시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 128 51 44 40.000%

문제

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

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

수열 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
W3sicHJvYmxlbV9pZCI6IjQ5MjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWM1ZjQgXHVhYzc3XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWFlMzhcdWM3NzRcdWFjMDAgXHVjNzIwXHVkNTVjXHVkNTU4XHVhY2UwLCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWMgXHVjMjFjXHVjMTFjXHViODVjIFx1YjQxOFx1YzViNFx1Yzc4OFx1YjI5NCBcdWI0NTAgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YzIxOFx1YzVmNFx1YzVkMCBcdWFjZjVcdWQxYjVcdWM3M2NcdWI4NWMgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzZkMFx1YzE4Y1x1YjI5NCBcdWFkNTBcdWNjMjhcdWM4MTBcdWM3M2NcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90d29zZXEucG5nXCIgc3R5bGU9XCJ3aWR0aDogMTUzcHg7IGhlaWdodDogMzU0cHg7IGZsb2F0OiByaWdodDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNTQ0XHViNzk4XHViMjk0IFx1YjQ1MCBcdWMyMThcdWM1ZjRcdWFjZmMgXHVhZDUwXHVjYzI4XHVjODEwXHVjNzQwIFx1YWQ3NVx1YWM4YyBcdWIwOThcdWQwYzBcdWIwYjggXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMyMThcdWM1ZjQgMSA9IDMgNSA8c3Ryb25nPjc8XC9zdHJvbmc+IDkgMjAgPHN0cm9uZz4yNTxcL3N0cm9uZz4gMzAgNDAgPHN0cm9uZz41NTxcL3N0cm9uZz4gNTYgPHN0cm9uZz41NzxcL3N0cm9uZz4gNjAgNjI8XC9wPlxyXG48cD5cclxuXHRcdWMyMThcdWM1ZjQgMiA9IDEgNCA8c3Ryb25nPjc8XC9zdHJvbmc+IDExIDE0IDxzdHJvbmc+MjU8XC9zdHJvbmc+IDQ0IDQ3IDxzdHJvbmc+NTU8XC9zdHJvbmc+IDxzdHJvbmc+NTc8XC9zdHJvbmc+IDEwMDxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3NzQgXHViNDUwIFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YWM3OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQxLiBcdWI0NTAgXHVjMjE4XHVjNWY0XHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWNjYWJcdWJjODhcdWM5ZjggXHVjNmQwXHVjMThjXHVjNWQwXHVjMTFjIFx1YWM3N1x1YWUzMFx1Yjk3YyBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YWM3N1x1YjI5NCBcdWFjODNcdWM3NDAgXHVjNTVlXHVjNzNjXHViODVjXHViOWNjIFx1YWM3OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbjxwPlxyXG5cdDIuIFx1YWQ1MFx1Y2MyOFx1YzgxMFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1ODhcdWM3NDQgXHViNTRjXHViMjk0LCBcdWQ2MDRcdWM3YWMgXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjIFx1YWNjNFx1YzE4ZCBcdWFjNzhcdWM3NDRcdWM5YzAsIFx1YjJlNFx1Yjk3OCBcdWMyMThcdWM1ZjRcdWI4NWMgXHVhYzA4XHVjNTQ0XHVkMGM4XHVjOWMwIFx1YWNiMFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJjMjlcdWJiMzhcdWQ1NWMgXHVjMjJiXHVjNzkwXHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjNzA0XHVjNzU4IFx1YzYwOFx1YzVkMFx1YzExYyAzLCA1LCA3LCA5LCAyMCwgMjUsIDQ0LCA0NywgNTUsIDU2LCA1NywgNjBcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YWM3N1x1YjI5NFx1YjJlNFx1YmE3NCBcdWQ1NjlcdWM3NzQgNDUwXHVjNzNjXHViODVjIFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWI0NTAgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWMwMSBcdWM5MDRcdWM3NTggXHVjY2FiXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzc0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVjNmQwXHVjMThjXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMVx1Yzc3NFx1YzBjMVx1Yzc3NFx1YWNlMCwgMTAsMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YzIxOFx1YzVmNFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YzIxOFx1YjI5NCAtMTAsMDAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDkyOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRoZSBEb3VibGUgSGVMaVgiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHdvc2VxLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDozNTRweDsgd2lkdGg6MTUzcHhcIiBcLz5Ud28gZmluaXRlLCBzdHJpY3RseSBpbmNyZWFzaW5nLCBpbnRlZ2VyIHNlcXVlbmNlcyBhcmUgZ2l2ZW4uIEFueSBjb21tb24gaW50ZWdlciBiZXR3ZWVuIHRoZSB0d28gc2VxdWVuY2VzIGNvbnN0aXR1dGUgYW4gaW50ZXJzZWN0aW9uIHBvaW50LiBUYWtlIGZvciBleGFtcGxlIHRoZSBmb2xsb3dpbmcgdHdvIHNlcXVlbmNlcyB3aGVyZSBpbnRlcnNlY3Rpb24gcG9pbnRzIGFyZSBwcmludGVkIGluIGJvbGQ6PFwvcD5cclxuXHJcbjxwPkZpcnN0PSAzIDUgNyA5IDIwIDI1IDMwIDQwIDU1IDU2IDU3IDYwIDYyPGJyIFwvPlxyXG5TZWNvbmQ9IDEgNCA3IDExIDE0IDI1IDQ0IDQ3IDU1IDU3IDEwMDxcL3A+XHJcblxyXG48cD5Zb3UgY2FuICZxdW90O3dhbGsmcXVvdDsgb3ZlciB0aGVzZSB0d28gc2VxdWVuY2VzIGluIHRoZSBmb2xsb3dpbmcgd2F5OjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPllvdSBtYXkgc3RhcnQgYXQgdGhlIGJlZ2lubmluZyBvZiBhbnkgb2YgdGhlIHR3byBzZXF1ZW5jZXMuIE5vdyBzdGFydCBtb3ZpbmcgZm9yd2FyZC48XC9saT5cclxuXHQ8bGk+QXQgZWFjaCBpbnRlcnNlY3Rpb24gcG9pbnQsIHlvdSBoYXZlIHRoZSBjaG9pY2Ugb2YgZWl0aGVyIGNvbnRpbnVpbmcgd2l0aCB0aGUgc2FtZSBzZXF1ZW5jZSB5b3UmIzM5O3JlIGN1cnJlbnRseSBvbiwgb3Igc3dpdGNoaW5nIHRvIHRoZSBvdGhlciBzZXF1ZW5jZS48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5UaGUgb2JqZWN0aXZlIGlzIGZpbmRpbmcgYSBwYXRoIHRoYXQgcHJvZHVjZXMgdGhlIG1heGltdW0gc3VtIG9mIGRhdGEgeW91IHdhbGtlZCBvdmVyLiBJbiB0aGUgYWJvdmUgZXhhbXBsZSwgdGhlIGxhcmdlc3QgcG9zc2libGUgc3VtIGlzIDQ1MCB3aGljaCBpcyB0aGUgcmVzdWx0IG9mIGFkZGluZyAzLCA1LCA3LCA5LCAyMCwgMjUsIDQ0LCA0NywgNTUsIDU2LCA1NywgNjAsIGFuZCA2MjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIHdpbGwgYmUgdGVzdGVkIG9uIGEgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIHdpbGwgYmUgc3BlY2lmaWVkIG9uIHR3byBzZXBhcmF0ZSBsaW5lcy4gRWFjaCBsaW5lIGRlbm90ZXMgYSBzZXF1ZW5jZSBhbmQgaXMgc3BlY2lmaWVkIHVzaW5nIHRoZSBmb2xsb3dpbmcgZm9ybWF0OjxcL3A+XHJcblxyXG48cHJlPm4gdjEgdjIgLi4uIHZuPFwvcHJlPlxyXG5cclxuPHA+V2hlcmUgbiBpcyB0aGUgbGVuZ3RoIG9mIHRoZSBzZXF1ZW5jZSBhbmQgdmkgaXMgdGhlIGl0aCBlbGVtZW50IGluIHRoYXQgc2VxdWVuY2UuIEVhY2ggc2VxdWVuY2Ugd2lsbCBoYXZlIGF0IGxlYXN0IG9uZSBlbGVtZW50IGJ1dCBubyBtb3JlIHRoYW4gMTAsMDAwLiBBbGwgZWxlbWVudHMgYXJlIGJldHdlZW4gLTEwLDAwMCBhbmQgMTAsMDAwIChpbmNsdXNpdmUpLjxcL3A+XHJcblxyXG48cD5UaGUgbGFzdCBsaW5lIG9mIHRoZSBpbnB1dCBpbmNsdWRlcyBhIHNpbmdsZSB6ZXJvLCB3aGljaCBpcyBub3QgcGFydCBvZiB0aGUgdGVzdCBjYXNlcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHdyaXRlIG9uIGEgc2VwYXJhdGUgbGluZSwgdGhlIGxhcmdlc3QgcG9zc2libGUgc3VtIHRoYXQgY2FuIGJlIHByb2R1Y2VkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==