Informatica Online Judge

  빵 귀신 [2177 / 0881]

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


The Champion of this Problem (C++) : icp1481 - 174ms / 751byte
My Best Submission (C++) : N/A

[CCC2015S5]

Background

근처에 있는 빵 가게에서 몽땅-다-드세요! 할인 행사가 진행 중이기 때문에 그냥 지나칠 수가 없다.

가게 앞에는 $N$ 개의 빵이 왼쪽에서 오른쪽으로 가면서 한 줄로 놓여있다. - $i$번째 빵에는 $A_i$ 만큼의 설탕이 들어있다.

그리고 또 그 아래에 $M$ 개의 빵이 한 줄 더 놓여있고, 마찬가지로 $i$번째 빵에는 $B_i$ 만큼의 설탕이 들어있다.

아래에 있는 $M$ 개의 빵들을 위에 있는 $N$ 개 빵이 있는 줄 왼쪽/사이/오른쪽에 하나씩 모두 끼워 넣을 수 있다. 그렇게 아랫줄에 있는 빵들을 모두 끼워 넣으면, 원래 처음에 놓여 있던 $N$ 개의 빵 순서는 바뀌지 않은 상태로, $N+M$ 개의 빵들을 한 줄로 늘어놓을 수 있게 된다.

이렇게 만들고 난 후에는, 몽땅-다-드세요! 행사로서 왼쪽에서 오른쪽으로 순서대로 가면서 각 빵을 고를지/말지 선택해 담고 싸게 구입할 수 있다. 단! 오른쪽으로 빨리 움직여 가야하기 때문에 연속으로 2개를 주워 담을 수는 없다.

여러분들은 빵을 아주 좋아하고 잘 아는 빵 귀신이기 때문에, 구입한 빵에 들어있는 설탕들의 합을 최대한 많게 하고 싶다. 가능한 설탕의 최대량은 얼마까지 가능할까?

Input

첫 번째 줄에는 $N$이 입력된다.

그 다음 $N$개의 줄에 걸쳐 $i$번째 빵에 들어있는 설탕의 양 $A_i$가 입력된다.

그 다음 줄에는 $M$이 입력된다.

그 다음 $M$개의 줄에 걸쳐 $i$번째 빵에 들어있는 설탕의 양 $B_i$가 입력된다.

[입력값의 정의역]
$1<=N<=3,000$
$1<=A_i<=10^5$
$1<=M<=100$
$1<=B_i<=10^5$

Output

가능한 설탕의 최대량을 출력한다.

IO Example

입력 예시
5
10
12
6
14
7
3
1
8
2

출력 예시
44

*설명 : 1빵을 10 (1) 12 사이에 넣고, 8빵과 2빵을 12 (2) (8) 6 사이에 넣으면 10 1 12 2 8 6 14 7 이 된다. 그 다음에 10 + 12 + 8 + 14를 고르면 44 를 만들 수 있고 최대량이다.

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