Olympiad Training

题意翻译

/* ### 题目描述 安东决定为信息学奥赛做准备。伊利亚准备了几个任务让他去解决，且只能在前 $d_i$ 天完成第 $i$ 个任务。安东一天最多只能完成一项任务。伊利亚提供的第 $i$ 个任务价值为 $r_i$ ，并将任务分为三个主题，第 $i$ 个任务的主题是$type_i$。安东想要解决第一个主题的 $a$ 个任务，第二个主题的 $b$ 个任务，第三个主题的 $c$ 个任务。 请你帮安东得出是否能够这样做，如果可以，计算他可以解决的任务的最大价值之和。 ### 输入格式 第一行，一个整数 $t(1 \leq t \leq 10^4)$ 表示测试数据个数。 对于每个数据，第一行四个整数 $n(1 \leq n \leq 10^5)$, $a$, $b$, $c(0 \leq a,b,c \leq n)$ ，接下来的 $n$ 行每行都包含三个整数 $r_i$ , $type_i$ , $d_i(0\leq r_i \leq 10^9 , 1 \leq type_i \leq 3 , 1 \leq d_i \leq n) $ 。 $ \sum{n} \leq 10^5 $ ### 输出格式 对于每个测试用例，如果安东不能达到他的目标，打印 ```-1``` ;否则，打印他将解决的任务的最大有用性。 */

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #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

说明

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 $ .

题目大意：
Anton 准备参加信息学奥赛，Ilya 为他准备了 n 个任务。第 i 个任务只能在最初 d_i 天内提交答案，Anton 每天最多完成一个任务。每个任务的价值为 r_i，分为三个主题，第 i 个任务的主题是 type_i。Anton 想要完成第一个主题的 a 个任务，第二个主题的 b 个任务，第三个主题的 c 个任务。需要判断是否能完成这些任务，如果可以，计算他可以解决的任务的最大价值之和。

输入输出数据格式：
输入格式：
- 第一行，一个整数 t(1 ≤ t ≤ 10^4)，表示测试数据个数。
- 对于每个数据，第一行四个整数 n(1 ≤ n ≤ 10^5), a, b, c(0 ≤ a,b,c ≤ n)。
- 接下来的 n 行每行都包含三个整数 r_i, type_i, d_i(0≤ r_i ≤ 10^9, 1 ≤ type_i ≤ 3, 1 ≤ d_i ≤ n)。∑n ≤ 10^5

输出格式：
- 对于每个测试用例，如果 Anton 不能达到他的目标，打印 -1；否则，打印他将解决的任务的最大有用性。题目大意： Anton 准备参加信息学奥赛，Ilya 为他准备了 n 个任务。第 i 个任务只能在最初 d_i 天内提交答案，Anton 每天最多完成一个任务。每个任务的价值为 r_i，分为三个主题，第 i 个任务的主题是 type_i。Anton 想要完成第一个主题的 a 个任务，第二个主题的 b 个任务，第三个主题的 c 个任务。需要判断是否能完成这些任务，如果可以，计算他可以解决的任务的最大价值之和。 输入输出数据格式： 输入格式： - 第一行，一个整数 t(1 ≤ t ≤ 10^4)，表示测试数据个数。 - 对于每个数据，第一行四个整数 n(1 ≤ n ≤ 10^5), a, b, c(0 ≤ a,b,c ≤ n)。 - 接下来的 n 行每行都包含三个整数 r_i, type_i, d_i(0≤ r_i ≤ 10^9, 1 ≤ type_i ≤ 3, 1 ≤ d_i ≤ n)。∑n ≤ 10^5 输出格式： - 对于每个测试用例，如果 Anton 不能达到他的目标，打印 -1；否则，打印他将解决的任务的最大有用性。