P16882 [GKS 2022 #D] Maximum Gain

Charles 正在参加 Crowdsource 任务活动，他非常渴望从中获得最高分！共有两个 Crowdsource 任务：音频验证任务和图像标注任务。每个任务包含一系列问题。Charles 得到了两个数组（$A$ 和 $B$），分别代表这两个任务。数组的每个元素表示 Charles 回答对应问题所能获得的分数。 Charles 总共可以回答 $K$ 个问题（从两个任务中选出），一次回答一个。每一步，他可以选择一个还有未回答问题的任务（即选择两个数组中的一个），然后从该任务的剩余问题列表中，选择第一个或最后一个问题来回答。一旦他回答了问题，就会获得相应的分数，并且该问题会从任务中移除。 你能帮助 Charles 选择问题，使他获得尽可能高的分数吗？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含一个整数 $N$，表示第一个数组的元素个数。 第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$。$A_i$ 表示回答音频验证任务中第 $i$ 个问题所获得的分数。 第三行包含一个整数 $M$，表示第二个数组的元素个数。 第四行包含 $M$ 个整数 $B_1, B_2, \ldots, B_M$。$B_i$ 表示回答图像标注任务中第 $i$ 个问题所获得的分数。 第五行包含一个整数 $K$，表示按照上述过程从两个数组中总共要选择的问题数量。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Charles 在此测试用例中能获得的最大分数。

在样例 #1 中，Charles 可以回答 $5$ 个问题。如果他从第一个数组中选择第一个和最后一个问题，他将获得 $(3 + 2)$ 分。如果他从第二个数组中选择前两个问题和最后一个问题，他将获得 $(2 + 8 + 9)$ 分。因此，通过回答这 $5$ 个问题，Charles 获得 $((3 + 2) + (2 + 8 + 9)) = 24$ 分。这恰好是该测试用例中 Charles 能获得的最大分数。一个非最优的选择是：从第一个数组中选择最后两个元素，从第二个数组中选择第一个元素和最后两个元素，这样将得到 $((1 + 2) + (2 + 1 + 9)) = 15$ 分。 在样例 #2 中，Charles 可以回答 $6$ 个问题。如果他从第一个数组中选择前两个问题，他将获得 $(1 + 100)$ 分。如果他从第二个数组中选择前三个问题和最后一个问题，他将获得 $(15 + 10 + 12 + 10)$ 分。因此，选择这 $6$ 个问题，Charles 获得 $((1 + 100) + (15 + 10 + 12 + 10)) = 148$ 分，这恰好是该测试用例中的最大值。 ### 限制条件 $1 \le T \le 100$。 $1 \le N \le 6000$。 $1 \le M \le 6000$。 对于所有 $i$，$1 \le A_i, B_i \le 10^9$。 $1 \le K \le N + M$。 **测试集 1** $1 \le K \le 30$。 **测试集 2** $1 \le K \le 3000$。 翻译由 DeepSeek V4 Pro 完成