安东决定为信息学奥林匹克竞赛做好准备。 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$$$ 是最佳选择。