Informatica Online Judge

  BAKEJOON [2279 / 08E7]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 8   Total Tried : 10


The Champion of this Problem (C++) : gs16103 - 36ms / 1346byte
My Best Submission (C++) : N/A

[]

Background

찬호는 BAKEJOON ONLINE JUDGE의 문제집 시스템에 깊은 감명을 받았다! 찬호는 BAKEJOON ONLINE JODGE에 있는 문제집을 골라 문제들을 풀려고 한다.

BAKEJOON ONLINE JUDGE에는 N개의 문제집이 위에서 아래로 나열되어 있으며, 이 중 i번째 문제집은 Ai개의 문제를 가지고 있다. 추가적으로 찬호가 만든 M개의 문제집이 있으며, 이 중 i번째 문제집은 Bi개의 문제를 가지고 있다.

찬호는 먼저 위에서 아래로 나열되어 있는 N개의 문제집 사이에 자신이 만든 M개의 문제집을 아무 곳에나 (시작점, 끝점, 문제집 사이) 끼워 넣을 수 있다. 이렇게 되면 N+M 개의 문제집이 위에서 아래로 나열되며 초기의 N 개 문제집은 상대적 순서를 유지하는 형태가 될 것이다.

찬호는 이렇게 만들어 놓은 리스트에서 문제집들을 위에서 아래로 클릭하면서 선택한다. 찬호는 리스트에 있는 문제집을 선택할 수도 있고, 않을 수도 있지만, 찬호의 마우스 감도가 큰 편이기 때문에 만약에 한 문제집을 선택했다면 그 다음 문제집은 선택할 수 없다. 즉, 리스트에서 연속된 문제집을 고를 수 없다.

찬호가 문제를 가장 많이 풀 수 있도록, 찬호를 도와주자!

Input

첫 번째 줄에는 N (1 ≤ N ≤ 3,000) 이 주어진다. 이후 N개의 줄에 Ai (1 ≤ Ai ≤ 100,000) 가 주어진다.

N+2번째 줄에는 M (0 ≤ M ≤ 100) 이 주어진다. 이후 M개의 줄에 Bi (1 ≤ Bi ≤ 100,000) 가 주어진다.

Output

찬호가 최대로 풀 수 있는 정보 문제의 개수를 출력하라.

IO Example

IO Example
입력
5
10
12
6
14
7
3
1
8
2

출력
44

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]