CF1746G.Olympiad Training

Anton decided to get ready for an Olympiad in Informatics. Ilya prepared $n$ tasks for him to solve. It is possible to submit the solution for the $i$-th task in the first $d_{i}$ days only. Anton cannot solve more than one task a day. Ilya estimated the usefulness of the $i$-th tasks as $r_{i}$ and divided the tasks into three topics, the topic of the $i$-th task is $type_{i}$.

Anton wants to solve exactly $a$ tasks on the first topic, $b$ tasks on the second topic and $c$ tasks on the third topic. Tell Anton if it is possible to do so, and if it is, calculate the maximum total usefulness of the tasks he may solve.

安东决定为信息学奥林匹克竞赛做准备。伊利亚为他准备了 $n$ 道题目供其求解。第 $i$ 道题仅能在前 $d_{i}$ 天内提交解答。安东每天最多只能求解一道题。伊利亚将第 $i$ 道题的有用性估计为 $r_{i}$，并将所有题目分为三类主题，其中第 $i$ 道题所属的主题为 $type_{i}$。

安东希望恰好求解 $a$ 道第一类主题的题目、$b$ 道第二类主题的题目以及 $c$ 道第三类主题的题目。请判断安东能否实现这一目标；若可以，请计算他所能获得的最大总有用性。

The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains four integers $n, a, b, c$ ($1 \le n \le 10^5$, $0 \le a, b, c \le n$).

The following $n$ lines contain three integers each — $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$).

The sum of $n$ over all test cases does not exceed $10^5$.

输入的第一行包含一个整数 $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$。

For each test case print $-1$ if Anton cannot reach his goal; otherwise, print the maximum usefulness of the tasks he will solve.

如果 Anton 无法达成目标，则针对每个测试用例输出 $-1$；否则，输出他将解决的任务的最大实用性。

In the first test case from the sample test Anton can solve tasks $2$ and $4$.

In the second test case from the sample test it is impossible to fulfill Anton's wish.

In the third test case from the sample test it is optimal to solve tasks $2$, $3$ and $4$.

In the last test case from the sample test it is optimal to solve tasks $1$, $2$ and $4$.

在样例测试的第一个测试用例中，安东可以解决第 $2$ 和第 $4$ 个任务。

在样例测试的第二个测试用例中，无法满足安东的愿望。

在样例测试的第三个测试用例中，最优策略是解决第 $2$、$3$ 和 $4$ 个任务。

在样例测试的最后一个测试用例中，最优策略是解决第 $1$、$2$ 和 $4$ 个任务。