← 返回题目列表

Codeforces · 1746/G

G. 奥林匹克训练

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

安东决定为信息学奥林匹克竞赛做好准备。 Ilya 为他准备了 $$$n$$$ 任务来解决。可以仅在前 $$$d_{i}$$$ 天内提交第 $$$i$$$ 任务的解决方案。安东一天只能解决一项任务。 Ilya 将第 $$$i$$$ 个任务的有用性估计为 $$$r_{i}$$$ 并将任务分为三个主题,第 $$$i$$$ 个任务的主题是 $$$type_{i}$$$。

Anton 希望准确解决第一个主题的 $$$a$$$ 任务、第二个主题的 $$$b$$$ 任务以及第三个主题的 $$$c$$$ 任务。告诉安东是否可以这样做,如果可以,请计算他可以解决的任务的最大总有用性。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含四个整数 $$$n, a, b, c$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le a, b, c \le n$$$)。

以下 $$$n$$$ 行每行包含三个整数 — $$$r_i、type_i、d_i$$$ ($$$0 \le r_i \le 10^{9}$$$、$$$1 \le type_i \le 3$$$、$$$1 \le d_i \le n$$$)。

所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,如果 Anton 无法达到目标,则打印 $$$-1$$$;否则,打印他将解决的任务的最大用处。

示例

输入 #1

4
4 1 1 0
1 2 1
1 1 1
0 1 2
1 2 2
3 1 1 1
1 1 2
7 2 1
9 3 2
4 2 1 0
100 2 1
5 2 3
7 1 2
5 1 2
5 1 1 1
10 3 1
9 2 3
20 1 1
16 1 4
1 3 4

输出 #1

2
-1
17
35

注意

在示例测试的第一个测试用例中,Anton 可以解决任务 $$$2$$$ 和 $$$4$$$。

在样本测试的第二个测试用例中,不可能满足 Anton 的愿望。

在示例测试的第三个测试用例中,最佳解决任务 $$$2$$$、$$$3$$$ 和 $$$4$$$。

在示例测试的最后一个测试用例中,解决任务 $$$1$$$、$$$2$$$ 和 $$$4$$$ 是最佳选择。