{"trustable":false,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tTwo \u003cspan data-scayt_word\u003d\"finite\" data-scaytid\u003d\"1\"\u003efinite\u003c/span\u003e, strictly increasing, integer sequences are given. Any common integer between the two sequences constitute an intersection point. Take for example the following two sequences where intersection points are\u003c/p\u003e\r\n\u003cp\u003e\r\n\tprinted in bold:\u003cbr /\u003e\r\n\tFirst\u003d 3 5 \u003cstrong\u003e7\u003c/strong\u003e 9 20 \u003cstrong\u003e25\u003c/strong\u003e 30 40 \u003cstrong\u003e55\u003c/strong\u003e 56 \u003cstrong\u003e57\u003c/strong\u003e 60 62\u003cbr /\u003e\r\n\tSecond\u003d 1 4 \u003cstrong\u003e7\u003c/strong\u003e 11 14 \u003cstrong\u003e25\u003c/strong\u003e 44 47 \u003cstrong\u003e55\u003c/strong\u003e \u003cstrong\u003e57\u003c/strong\u003e 100\u003cbr /\u003e\r\n\tYou can \u0026lsquo;walk\u0026rdquo; over these two sequences in the following way:\u003cbr /\u003e\r\n\t1. You may start at the beginning of any of the two sequences. Now start moving forward.\u003cbr /\u003e\r\n\t2. At each intersection point, you have the choice of either continuing with the same sequence you\u0026rsquo;re currently on, or switching to the other sequence.\u003cbr /\u003e\r\n\tThe objective is \u003cspan data-scayt_word\u003d\"finding\" data-scaytid\u003d\"2\"\u003efinding\u003c/span\u003e a path that produces the maximum sum of data you walked over. In the above example, the largest possible sum is 450\u0026nbsp; which is the result of adding 3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, and 62\u003c/p\u003e\r\n\u003ch3\u003e\r\n\tInput\u003c/h3\u003e\r\n\u003cp\u003e\r\n\tYour program will be tested on a number of test cases. Each test case will be \u003cspan data-scayt_word\u003d\"specified\" data-scaytid\u003d\"3\"\u003especified\u003c/span\u003e on two separate lines. Each line denotes a sequence and is \u003cspan data-scayt_word\u003d\"specified\" data-scaytid\u003d\"4\"\u003especified\u003c/span\u003e using the following format:\u003c/p\u003e\r\n\u003cpre\u003e\r\n\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; n\u0026nbsp; v1 v2 ... vn\u003c/pre\u003e\r\n\u003cp\u003e\r\n\tWhere n is the length of the sequence and vi is the ith element in that sequence. Each sequence will have at least one element but no more than 10,000. All elements are between -10,000 and 10,000 (inclusive).\u003cbr /\u003e\r\n\tThe last line of the input includes a single zero, which is not part of the test cases.\u003c/p\u003e\r\n\u003ch3\u003e\r\n\tOutput\u003c/h3\u003e\r\n\u003cp\u003e\r\n\tFor each test case, write on a separate line, the largest possible sum that can be produced.\u003c/p\u003e\r\n\u003ch3\u003e\r\n\tSample\u003c/h3\u003e\r\n\u003cpre\u003e\r\ninput \r\n\u0026nbsp;\r\n13 3 5 7 9 20 25 30 40 55 56 57 60 62\r\n11 1 4 7 11 14 25 44 47 55 57 100\r\n4 -5 100 1000 1005\r\n3 -12 1000 1001\r\n0\r\noutput \r\n\u0026nbsp;\r\n450\r\n2100\r\n\u003c/pre\u003e"}}]}