시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 241 95 67 35.638%

문제

길이가 유한하고, 오름차순 순서로 되어있는 두 수열이 주어진다. 두 수열에 공통으로 들어있는 원소는 교차점으로 생각할 수 있다.

아래는 두 수열과 교차점은 굵게 나타낸 것이다.

수열 1 = 3 5 7 9 20 25 30 40 55 56 57 60 62

수열 2 = 1 4 7 11 14 25 44 47 55 57 100

이 두 수열은 다음과 같이 걸을 수 있다.

  1. 두 수열중 하나의 첫 번째 원소에서 걷기를 시작한다. 걷는 것은 앞으로만 걸을 수 있다.
  2. 교차점에 도착했을 때는, 현재 수열에서 계속 걸을지, 다른 수열로 갈아탈지 결정할 수 있다.

방문한 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하시오. 위의 예에서 3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, 62와 같이 걷는다면 합이 450으로 최대가 된다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 두 줄로 이루어져 있다.

각 줄의 첫 번째 수는 수열의 길이이다. 그 다음에는 수열의 원소가 순서대로 주어진다. 수열의 길이는 1이상이고, 10,000을 넘지 않는다. 수열에 들어있는 모든 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 얻을 수 있는 최대 합을 출력한다.

예제 입력 1

13 3 5 7 9 20 25 30 40 55 56 57 60 62
11 1 4 7 11 14 25 44 47 55 57 100
4 -5 100 1000 1005
3 -12 1000 1001
0

예제 출력 1

450
2100
W3sicHJvYmxlbV9pZCI6IjQ5MjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWM1ZjQgXHVhYzc3XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFlMzhcdWM3NzRcdWFjMDAgXHVjNzIwXHVkNTVjXHVkNTU4XHVhY2UwLCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWMgXHVjMjFjXHVjMTFjXHViODVjIFx1YjQxOFx1YzViNFx1Yzc4OFx1YjI5NCBcdWI0NTAgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YzIxOFx1YzVmNFx1YzVkMCBcdWFjZjVcdWQxYjVcdWM3M2NcdWI4NWMgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzZkMFx1YzE4Y1x1YjI5NCBcdWFkNTBcdWNjMjhcdWM4MTBcdWM3M2NcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3VwbG9hZFwvaW1hZ2VzXC90d29zZXEucG5nXCIgc3R5bGU9XCJ3aWR0aDogMTUzcHg7IGhlaWdodDogMzU0cHg7IGZsb2F0OiByaWdodDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4XHViMjk0IFx1YjQ1MCBcdWMyMThcdWM1ZjRcdWFjZmMgXHVhZDUwXHVjYzI4XHVjODEwXHVjNzQwIFx1YWQ3NVx1YWM4YyBcdWIwOThcdWQwYzBcdWIwYjggXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWM1ZjQgMSA9IDMgNSA8c3Ryb25nPjc8XC9zdHJvbmc+IDkgMjAgPHN0cm9uZz4yNTxcL3N0cm9uZz4gMzAgNDAgPHN0cm9uZz41NTxcL3N0cm9uZz4gNTYgPHN0cm9uZz41NzxcL3N0cm9uZz4gNjAgNjI8XC9wPlxyXG5cclxuPHA+XHVjMjE4XHVjNWY0IDIgPSAxIDQgPHN0cm9uZz43PFwvc3Ryb25nPiAxMSAxNCA8c3Ryb25nPjI1PFwvc3Ryb25nPiA0NCA0NyA8c3Ryb25nPjU1PFwvc3Ryb25nPiA8c3Ryb25nPjU3PFwvc3Ryb25nPiAxMDA8XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YjQ1MCBcdWMyMThcdWM1ZjRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWFjNzhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWI0NTAgXHVjMjE4XHVjNWY0XHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzZkMFx1YzE4Y1x1YzVkMFx1YzExYyBcdWFjNzdcdWFlMzBcdWI5N2MgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWFjNzdcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YzU1ZVx1YzczY1x1Yjg1Y1x1YjljYyBcdWFjNzhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhZDUwXHVjYzI4XHVjODEwXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU4OFx1Yzc0NCBcdWI1NGNcdWIyOTQsIFx1ZDYwNFx1YzdhYyBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVhY2M0XHVjMThkIFx1YWM3OFx1Yzc0NFx1YzljMCwgXHViMmU0XHViOTc4IFx1YzIxOFx1YzVmNFx1Yjg1YyBcdWFjMDhcdWM1NDRcdWQwYzhcdWM5YzAgXHVhY2IwXHVjODE1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHViYzI5XHViYjM4XHVkNTVjIFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YjI5NCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzcwNFx1Yzc1OCBcdWM2MDhcdWM1ZDBcdWMxMWMgMywgNSwgNywgOSwgMjAsIDI1LCA0NCwgNDcsIDU1LCA1NiwgNTcsIDYwLCA2Mlx1YzY0MCBcdWFjMTlcdWM3NzQgXHVhYzc3XHViMjk0XHViMmU0XHViYTc0IFx1ZDU2OVx1Yzc3NCA0NTBcdWM3M2NcdWI4NWMgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViNDUwIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjOTA0XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjE4XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM1ZDBcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzZkMFx1YzE4Y1x1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDFcdWM3NzRcdWMwYzFcdWM3NzRcdWFjZTAsIDEwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWMyMThcdWM1ZjRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWMyMThcdWIyOTQgLTEwLDAwMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVkNTU4XHViMDk4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ5MjkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgRG91YmxlIEhlTGlYIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3R3b3NlcS5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MzU0cHg7IHdpZHRoOjE1M3B4XCIgXC8+VHdvIGZpbml0ZSwgc3RyaWN0bHkgaW5jcmVhc2luZywgaW50ZWdlciBzZXF1ZW5jZXMgYXJlIGdpdmVuLiBBbnkgY29tbW9uIGludGVnZXIgYmV0d2VlbiB0aGUgdHdvIHNlcXVlbmNlcyBjb25zdGl0dXRlIGFuIGludGVyc2VjdGlvbiBwb2ludC4gVGFrZSBmb3IgZXhhbXBsZSB0aGUgZm9sbG93aW5nIHR3byBzZXF1ZW5jZXMgd2hlcmUgaW50ZXJzZWN0aW9uIHBvaW50cyBhcmUgcHJpbnRlZCBpbiBib2xkOjxcL3A+XHJcblxyXG48cD5GaXJzdD0gMyA1IDcgOSAyMCAyNSAzMCA0MCA1NSA1NiA1NyA2MCA2MjxiciBcLz5cclxuU2Vjb25kPSAxIDQgNyAxMSAxNCAyNSA0NCA0NyA1NSA1NyAxMDA8XC9wPlxyXG5cclxuPHA+WW91IGNhbiAmcXVvdDt3YWxrJnF1b3Q7IG92ZXIgdGhlc2UgdHdvIHNlcXVlbmNlcyBpbiB0aGUgZm9sbG93aW5nIHdheTo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5Zb3UgbWF5IHN0YXJ0IGF0IHRoZSBiZWdpbm5pbmcgb2YgYW55IG9mIHRoZSB0d28gc2VxdWVuY2VzLiBOb3cgc3RhcnQgbW92aW5nIGZvcndhcmQuPFwvbGk+XHJcblx0PGxpPkF0IGVhY2ggaW50ZXJzZWN0aW9uIHBvaW50LCB5b3UgaGF2ZSB0aGUgY2hvaWNlIG9mIGVpdGhlciBjb250aW51aW5nIHdpdGggdGhlIHNhbWUgc2VxdWVuY2UgeW91JiMzOTtyZSBjdXJyZW50bHkgb24sIG9yIHN3aXRjaGluZyB0byB0aGUgb3RoZXIgc2VxdWVuY2UuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+VGhlIG9iamVjdGl2ZSBpcyBmaW5kaW5nIGEgcGF0aCB0aGF0IHByb2R1Y2VzIHRoZSBtYXhpbXVtIHN1bSBvZiBkYXRhIHlvdSB3YWxrZWQgb3Zlci4gSW4gdGhlIGFib3ZlIGV4YW1wbGUsIHRoZSBsYXJnZXN0IHBvc3NpYmxlIHN1bSBpcyA0NTAgd2hpY2ggaXMgdGhlIHJlc3VsdCBvZiBhZGRpbmcgMywgNSwgNywgOSwgMjAsIDI1LCA0NCwgNDcsIDU1LCA1NiwgNTcsIDYwLCBhbmQgNjI8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSB3aWxsIGJlIHRlc3RlZCBvbiBhIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSB3aWxsIGJlIHNwZWNpZmllZCBvbiB0d28gc2VwYXJhdGUgbGluZXMuIEVhY2ggbGluZSBkZW5vdGVzIGEgc2VxdWVuY2UgYW5kIGlzIHNwZWNpZmllZCB1c2luZyB0aGUgZm9sbG93aW5nIGZvcm1hdDo8XC9wPlxyXG5cclxuPHByZT5uIHYxIHYyIC4uLiB2bjxcL3ByZT5cclxuXHJcbjxwPldoZXJlIG4gaXMgdGhlIGxlbmd0aCBvZiB0aGUgc2VxdWVuY2UgYW5kIHZpIGlzIHRoZSBpdGggZWxlbWVudCBpbiB0aGF0IHNlcXVlbmNlLiBFYWNoIHNlcXVlbmNlIHdpbGwgaGF2ZSBhdCBsZWFzdCBvbmUgZWxlbWVudCBidXQgbm8gbW9yZSB0aGFuIDEwLDAwMC4gQWxsIGVsZW1lbnRzIGFyZSBiZXR3ZWVuIC0xMCwwMDAgYW5kIDEwLDAwMCAoaW5jbHVzaXZlKS48XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgbGluZSBvZiB0aGUgaW5wdXQgaW5jbHVkZXMgYSBzaW5nbGUgemVybywgd2hpY2ggaXMgbm90IHBhcnQgb2YgdGhlIHRlc3QgY2FzZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCB3cml0ZSBvbiBhIHNlcGFyYXRlIGxpbmUsIHRoZSBsYXJnZXN0IHBvc3NpYmxlIHN1bSB0aGF0IGNhbiBiZSBwcm9kdWNlZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=