수열 걷기

오름차순으로 정렬된 유한한 두 정수 수열이 주어진다. 두 수열에 공통으로 들어 있는 값은 두 수열이 만나는 교차점으로 볼 수 있다.

다음은 두 수열이며, 교차점은 굵게 표시했다.

• 수열 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. 더 이상 앞으로 갈 원소가 없을 때, 즉 지금 걷고 있는 수열의 마지막 원소에 도달하면 걷기가 끝난다.

걷는 동안 방문한 모든 원소의 합이 최대가 되도록 하는 경로의 합을 구하여라. 예를 들어 위의 두 수열에서 3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, 62 순서로 걸으면 합이 450이 되고, 이것이 얻을 수 있는 최대 합이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 줄이며, 한 줄이 하나의 수열을 나타낸다.

각 줄은 먼저 수열의 길이 $L$이 주어지고, 이어서 오름차순으로 정렬된 $L$개의 정수가 공백으로 구분되어 주어진다. 수열의 길이는 $1 \le L \le 10000$이고, 각 원소는 $-10000 \le a_i \le 10000$인 정수이다.

입력의 마지막 줄에는 $0$ 하나만 주어지며, 이는 입력의 끝을 의미한다.

각 테스트 케이스마다 걸어서 얻을 수 있는 최대 합을 한 줄에 하나씩 출력한다.