You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个长度为 $n$ 的序列 $a$ 和一个长度为 $m$ 的序列 $b$，你可以将 $b$ 序列中的元素任意插入到 $a$ 序列的任何位置（包括开头和末尾）。之后，你可以从新的序列中选一些元素，但你不能选择两个相邻的元素。

你需要使得你选出的数之和最大，输出这个最大值即可。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行一个整数 $a_{i}$。

接下来一行一个整数 $m$。

接下来 $m$ 行，每行一个整数 $b_{i}$。

输出格式

输出一行一个整数，表示你能选出元素和的最大值。

5
10
12
6
14
7
3
1
8
2

44

提示

【数据范围】：

对于 $20\%$ 的数据，$m = 0$。

对于另外 $20\%$ 的数据，$m = 1$。

对于另外 $20\%$ 的数据，$m \leq 10$。

对于 $100\%$ 的数据，$1 \leq n \leq 3 \times 10^{3}$，$0 \leq m \leq 100$，$1 \leq a_{i},b_{i} \leq 10^{5}$。