P9814 [CCC 2015 S5] Greedy For Pies

Given a sequence $a$ of length $n$ and a sequence $b$ of length $m$, you may insert the elements of sequence $b$ into sequence $a$ at any positions you like (including the beginning and the end). After that, you may choose some elements from the new sequence, but you are not allowed to choose two adjacent elements. You need to maximize the sum of the chosen numbers, and output this maximum value.

The first line contains an integer $n$. The next $n$ lines each contain an integer $a_{i}$. Then one line contains an integer $m$. The next $m$ lines each contain an integer $b_{i}$.

Output one line containing one integer, which is the maximum possible sum of elements you can choose.

**Constraints:** For $20\%$ of the testdata, $m = 0$. For another $20\%$ of the testdata, $m = 1$. For another $20\%$ of the testdata, $m \leq 10$. For $100\%$ of the testdata, $1 \leq n \leq 3 \times 10^{3}$, $0 \leq m \leq 100$, $1 \leq a_{i}, b_{i} \leq 10^{5}$. Translated by ChatGPT 5