시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 233 90 63 35.393%

문제

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

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

수열 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과 같이 걷는다면 합이 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
W3sicHJvYmxlbV9pZCI6IjQ5MjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWM1ZjQgXHVhYzc3XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFlMzhcdWM3NzRcdWFjMDAgXHVjNzIwXHVkNTVjXHVkNTU4XHVhY2UwLCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWMgXHVjMjFjXHVjMTFjXHViODVjIFx1YjQxOFx1YzViNFx1Yzc4OFx1YjI5NCBcdWI0NTAgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YzIxOFx1YzVmNFx1YzVkMCBcdWFjZjVcdWQxYjVcdWM3M2NcdWI4NWMgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzZkMFx1YzE4Y1x1YjI5NCBcdWFkNTBcdWNjMjhcdWM4MTBcdWM3M2NcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHdvc2VxLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDE1M3B4OyBoZWlnaHQ6IDM1NHB4OyBmbG9hdDogcmlnaHQ7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OFx1YjI5NCBcdWI0NTAgXHVjMjE4XHVjNWY0XHVhY2ZjIFx1YWQ1MFx1Y2MyOFx1YzgxMFx1Yzc0MCBcdWFkNzVcdWFjOGMgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMjE4XHVjNWY0IDEgPSAzIDUgPHN0cm9uZz43PFwvc3Ryb25nPiA5IDIwIDxzdHJvbmc+MjU8XC9zdHJvbmc+IDMwIDQwIDxzdHJvbmc+NTU8XC9zdHJvbmc+IDU2IDxzdHJvbmc+NTc8XC9zdHJvbmc+IDYwIDYyPFwvcD5cclxuXHJcbjxwPlx1YzIxOFx1YzVmNCAyID0gMSA0IDxzdHJvbmc+NzxcL3N0cm9uZz4gMTEgMTQgPHN0cm9uZz4yNTxcL3N0cm9uZz4gNDQgNDcgPHN0cm9uZz41NTxcL3N0cm9uZz4gPHN0cm9uZz41NzxcL3N0cm9uZz4gMTAwPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWI0NTAgXHVjMjE4XHVjNWY0XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVhYzc4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHViNDUwIFx1YzIxOFx1YzVmNFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NTggXHVjY2FiXHViYzg4XHVjOWY4IFx1YzZkMFx1YzE4Y1x1YzVkMFx1YzExYyBcdWFjNzdcdWFlMzBcdWI5N2MgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWFjNzdcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YzU1ZVx1YzczY1x1Yjg1Y1x1YjljYyBcdWFjNzhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhZDUwXHVjYzI4XHVjODEwXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU4OFx1Yzc0NCBcdWI1NGNcdWIyOTQsIFx1ZDYwNFx1YzdhYyBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVhY2M0XHVjMThkIFx1YWM3OFx1Yzc0NFx1YzljMCwgXHViMmU0XHViOTc4IFx1YzIxOFx1YzVmNFx1Yjg1YyBcdWFjMDhcdWM1NDRcdWQwYzhcdWM5YzAgXHVhY2IwXHVjODE1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHViYzI5XHViYjM4XHVkNTVjIFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YjI5NCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzcwNFx1Yzc1OCBcdWM2MDhcdWM1ZDBcdWMxMWMgMywgNSwgNywgOSwgMjAsIDI1LCA0NCwgNDcsIDU1LCA1NiwgNTcsIDYwXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWFjNzdcdWIyOTRcdWIyZTRcdWJhNzQgXHVkNTY5XHVjNzc0IDQ1MFx1YzczY1x1Yjg1YyBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWI0NTAgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWM5MDRcdWM3NTggXHVjY2FiXHViYzg4XHVjOWY4IFx1YzIxOFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzc0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjXHVjNWQwXHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxXHVjNzc0XHVjMGMxXHVjNzc0XHVhY2UwLCAxMCwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjMjE4XHVjNWY0XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjMjE4XHViMjk0IC0xMCwwMDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0OTI5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIERvdWJsZSBIZUxpWCIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90d29zZXEucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjM1NHB4OyB3aWR0aDoxNTNweFwiIFwvPlR3byBmaW5pdGUsIHN0cmljdGx5IGluY3JlYXNpbmcsIGludGVnZXIgc2VxdWVuY2VzIGFyZSBnaXZlbi4gQW55IGNvbW1vbiBpbnRlZ2VyIGJldHdlZW4gdGhlIHR3byBzZXF1ZW5jZXMgY29uc3RpdHV0ZSBhbiBpbnRlcnNlY3Rpb24gcG9pbnQuIFRha2UgZm9yIGV4YW1wbGUgdGhlIGZvbGxvd2luZyB0d28gc2VxdWVuY2VzIHdoZXJlIGludGVyc2VjdGlvbiBwb2ludHMgYXJlIHByaW50ZWQgaW4gYm9sZDo8XC9wPlxyXG5cclxuPHA+Rmlyc3Q9IDMgNSA3IDkgMjAgMjUgMzAgNDAgNTUgNTYgNTcgNjAgNjI8YnIgXC8+XHJcblNlY29uZD0gMSA0IDcgMTEgMTQgMjUgNDQgNDcgNTUgNTcgMTAwPFwvcD5cclxuXHJcbjxwPllvdSBjYW4gJnF1b3Q7d2FsayZxdW90OyBvdmVyIHRoZXNlIHR3byBzZXF1ZW5jZXMgaW4gdGhlIGZvbGxvd2luZyB3YXk6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+WW91IG1heSBzdGFydCBhdCB0aGUgYmVnaW5uaW5nIG9mIGFueSBvZiB0aGUgdHdvIHNlcXVlbmNlcy4gTm93IHN0YXJ0IG1vdmluZyBmb3J3YXJkLjxcL2xpPlxyXG5cdDxsaT5BdCBlYWNoIGludGVyc2VjdGlvbiBwb2ludCwgeW91IGhhdmUgdGhlIGNob2ljZSBvZiBlaXRoZXIgY29udGludWluZyB3aXRoIHRoZSBzYW1lIHNlcXVlbmNlIHlvdSYjMzk7cmUgY3VycmVudGx5IG9uLCBvciBzd2l0Y2hpbmcgdG8gdGhlIG90aGVyIHNlcXVlbmNlLjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlRoZSBvYmplY3RpdmUgaXMgZmluZGluZyBhIHBhdGggdGhhdCBwcm9kdWNlcyB0aGUgbWF4aW11bSBzdW0gb2YgZGF0YSB5b3Ugd2Fsa2VkIG92ZXIuIEluIHRoZSBhYm92ZSBleGFtcGxlLCB0aGUgbGFyZ2VzdCBwb3NzaWJsZSBzdW0gaXMgNDUwIHdoaWNoIGlzIHRoZSByZXN1bHQgb2YgYWRkaW5nIDMsIDUsIDcsIDksIDIwLCAyNSwgNDQsIDQ3LCA1NSwgNTYsIDU3LCA2MCwgYW5kIDYyPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gd2lsbCBiZSB0ZXN0ZWQgb24gYSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2Ugd2lsbCBiZSBzcGVjaWZpZWQgb24gdHdvIHNlcGFyYXRlIGxpbmVzLiBFYWNoIGxpbmUgZGVub3RlcyBhIHNlcXVlbmNlIGFuZCBpcyBzcGVjaWZpZWQgdXNpbmcgdGhlIGZvbGxvd2luZyBmb3JtYXQ6PFwvcD5cclxuXHJcbjxwcmU+biB2MSB2MiAuLi4gdm48XC9wcmU+XHJcblxyXG48cD5XaGVyZSBuIGlzIHRoZSBsZW5ndGggb2YgdGhlIHNlcXVlbmNlIGFuZCB2aSBpcyB0aGUgaXRoIGVsZW1lbnQgaW4gdGhhdCBzZXF1ZW5jZS4gRWFjaCBzZXF1ZW5jZSB3aWxsIGhhdmUgYXQgbGVhc3Qgb25lIGVsZW1lbnQgYnV0IG5vIG1vcmUgdGhhbiAxMCwwMDAuIEFsbCBlbGVtZW50cyBhcmUgYmV0d2VlbiAtMTAsMDAwIGFuZCAxMCwwMDAgKGluY2x1c2l2ZSkuPFwvcD5cclxuXHJcbjxwPlRoZSBsYXN0IGxpbmUgb2YgdGhlIGlucHV0IGluY2x1ZGVzIGEgc2luZ2xlIHplcm8sIHdoaWNoIGlzIG5vdCBwYXJ0IG9mIHRoZSB0ZXN0IGNhc2VzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgd3JpdGUgb24gYSBzZXBhcmF0ZSBsaW5lLCB0aGUgbGFyZ2VzdCBwb3NzaWJsZSBzdW0gdGhhdCBjYW4gYmUgcHJvZHVjZWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d