logo AlgoBeat OnlineJudge
登录 注册

#216252. [ECUSTPC 2025] 秋色堡垒

内存限制:1024 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

Maddy 来到了秋天的堡垒之前,在此她采集了 个食材,这些食材的新鲜度分别为
Maddy 会用这些食材做若干天的晚饭,特别的,因为她只有两个技艺值分别为 的食谱,她每天会做且只会做两道菜,少一道都不行哦。
每一天做饭的流程如下:

  • Maddy 可以以任意顺序选取两个不同未被选择过的食材,记其新鲜度分别为 ,随后对其进行烹饪,每个食材对应一个食谱,所制作出的菜肴的美味值分别为 ,则当天晚饭总的美味值为 ,注意 Maddy 可以以任意顺序选择食材对应的食谱,且每天晚饭必须选择 2 个不同的食材制作 2 道菜肴。

请帮助 Maddy 选取做晚饭的天数并求出在最优的情况下,这几天晚饭的总美味值 。(当然如果都太难吃了也可以不做的,换言之可以取天数为 。)

输入格式

第一行输入一个整数 (),表示数据组数。
每组测试数据输入的第一行输入 3 个整数 (),分别表示食材的个数以及两个食谱的技艺值。
随后一行输入 个整数 (),分别表示食材的新鲜度。
保证所有测试数据输入中的

输出格式

每组测试数据输出一行一个整数 ,表示在最优的情况下,这几天晚饭的总美味值。

样例

样例输入 1

6
4 1 2
4 5 6 7
5 2 8
0 -1 -2 -6 7
6 -1 -2
1 2 3 4 5 6
6 3 4
-1 0 0 1 2 3
6 -3 -4
1 0 0 -1 -2 -3
5 1 -10
-9 2 -5 3 -7

样例输出 1

35
56
0
23
23
165

数据范围与提示

样例 1 解释

对于第 1 个样例,我们考虑做 2 天的晚饭,其中:

  • 第一天选用新鲜度分别为 的食材分别对应技艺值为 的菜谱,可以烹饪出美味值为 的晚饭;
  • 第二天选用新鲜度分别为 的食材分别对应技艺值为 的菜谱,可以烹饪出美味值为 的晚饭。

总的美味值为
对于第 2 个样例,我们考虑做 1 天的晚饭,其中选用新鲜度分别为 的食材分别对应技艺值为 的菜谱,可以烹饪出美味值为 的晚饭。
对于第 3 个样例,我们考虑不做晚饭,因为任何情况下做出的晚饭的美味值均是负的。