← 返回题目列表

Codeforces · 2132/E

E. 算术比赛

中文机器翻译题面 查看原题

在算术比赛中,参赛者需要从他们拥有的卡片中获得尽可能高的总和。在团队中 “fst_ezik”,Vadim 有 $$$n$$$ 牌,号码为 $$$a_i$$$,Kostya 有 $$$m$$$ 牌,号码为 $$$b_i$$$。在每一轮$$$q$$$中,他们都想获胜,但这一次的比赛规则与平常略有不同。

在每一轮中,参与者都会获得三个数字 $$$x_i$$$、$$$y_i$$$ 和 $$$z_i$$$。团队 “fst_ezik” 必须从他们拥有的所有牌中准确选择$$$z_i$$$牌,但Vadim可以从他的牌组中选择不超过$$$x_i$$$牌,而Kostya可以从他的牌组中选择不超过$$$y_i$$$牌。帮助他们找到每一轮 $$$q$$$ 中可能的最高金额。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 测试用例的数量。测试用例的描述如下。

在每个测试用例的第一行,给出三个整数 $$$n$$$、$$$m$$$、$$$q$$$ $$$(1 \le n, m \le 2 \cdot 10^5, 1 \le q \le 10^5)$$$ - Vadim 拥有的牌数、Kostya 拥有的牌数以及比赛的轮数。

第二行包含 $$$n$$$ 整数 $$$a_i$$$ - Vadim 卡片上的数字 $$$(1 \le a_i \le 10^9)$$$。

第三行包含 $$$m$$$ 整数 $$$b_i$$$ — Kostya 卡片上的数字 $$$(1 \le b_i \le 10^9)$$$。

以下 $$$q$$$ 行用三个整数描述回合 $$$x_i$$$, $$$y_i$$$, $$$z_i$$$ $$$(0 \le x_i \le n, 0 \le y_i \le m, 0 \le z_i \le x_i + y_i)$$$ — 卡牌数量限制 Vadim可以选择的卡片数量、Kostya 可以选择的卡片数量的限制以及他们需要一起选择的卡片数量。

保证所有测试用例的$$$n$$$总和不超过$$$2 \cdot 10^5$$$,所有测试用例的$$$m$$$总和不超过$$$2 \cdot 10^5$$$,所有测试用例的$$$q$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,输出 $$$q$$$ 数字 — 相应轮次的最高可能总和。

示例

输入
复制

4
3 4 5
10 20 30
1 2 3 4
0 0 0
3 4 7
3 4 4
1 4 4
2 2 4
5 5 2
500000000 300000000 100000000 900000000 700000000
800000000 400000000 1000000000 600000000 200000000
1 4 3
5 2 6
4 4 1
100 100 20 20
100 100 20 20
4 4 5
3 3 6
2 363 711
286 121 102
1 1 1
3 1 1
1 2 0
1 3 2
0 1 0
3 3 3

输出
复制

0
70
64
39
57
2700000000
4200000000
420
711
711
0
997
0
1360