Olympiad Training
Contest: Codeforces Global Round 23
Difficulty rating: 3500
Tags: binary search, data structures, dp, flows, geometry, implementation, sortings

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.

Input format:
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$$$.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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

Example input:
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

Example output:
2
-1
17
35

Editorial:
Consider all subsets of the original set in which tasks can be performed in some order to satisfy the constraints on their completion, and also that the size of each of them does not exceed $$$a+b+c$$$. It is easy to show that this set is a weighted matroid. This means that the optimal set of tasks can be found using a greedy algorithm.
So, we can find a set of tasks with maximum total usefulness, which:
• satisfies all deadline constraints
• has no more than $$$a+b+c$$$ elements
For the given parameters $$$(x, y, z)$$$, we introduce the following transformation:
• Increase the usefulness of all tasks of the first type by $$$x$$$, the second type — by $$$y$$$, and the third type — by $$$z$$$.
Let's assume that the optimal solution after the transformation is described by the triple $$$[a',b',c']$$$ — the number of problems of each type, respectively. We need to get a solution described by the triple $$$[a,b,c]$$$. For $$$[a,b,c] \neq [a',b',c']$$$, $$$a+b+c=a'+b'+c'$$$ holds. Then (without limitation of generality, since there are at least two inequalities among $$$a\vee a',b\vee b',c\vee c'$$$) we assume that $$$a'>a,b'<b$$$.
Consider the following coordinate system on a two-dimensional plane (modulo the addition of $$$\overrightarrow{(1;1;1)})$$$:

For the coordinates of the point, we take the value $$$\vec{x}\times x+\vec{y}\times y + \vec{z}\times z$$$$$$(\vec{x}+\vec{y}+\vec{z} =\vec{0})$$$. It is easy to understand that the coordinates of the point $$$(x; y)$$$ on the plane are uniquely set by the triple $$$(x; y; z)$$$ up to the addition of $$$\overrightarrow{(1;1;1)} \times k, k \in\mathbb{Z}$$$
It is easy to show that there are parameters $$$(x,y,z)$$$ for which the optimal solution is unique and equal to $$$[a,b,c]$$$.
Consider the solution $$$[a',b',c']$$$ for the "center" of the current polygon (initially it is a hexagon with infinitely distant coordinates). The "center" is the center of the triangle formed by the middle lines of our polygon.
On this plane, decreasing $$$z$$$ or $$$y$$$ does not increase $$$b'+c'$$$, therefore, it does not decrease $$$a'$$$. Thus, the red area in the picture below does not suit us.
Increasing $$$x$$$ or $$$z$$$ does not decrease $$$a'+c'$$$, therefore, it does not increase $$$b'$$$. Because of this, the blue area in the picture below does not suit us either.

So, we need to cut off one half-plane along the $$$z$$$ axis. It can be shown that the area of the polygon under consideration decreases by a constant time for every 2-3 iterations.
But what if the number of emails of the desired color jumps from $$$a-1$$$ to $$$a+1$$$ at once? This is possible if and only if with the addition of some $$$x$$$ we get several pairs of elements of equal weight at the same time. To get rid of this, we can simply add a random number from $$$0$$$ to $$$\frac{1}{3}$$$ to each weight. The fact that such a change will fix the problem described above and will not change the optimal answer to the original problem remains to the reader as an exercise (the authors have proof).
After $$$O(\log C)$$$ iterations, our algorithm will converge to a point (a triple of real numbers). It remains only to check that the solution found is suitable for us.
$$$O(n\log n\log C)$$$