The water supply system in Gotham City consists of a system of $$$n$$$ subsystems of water towers. Subsystem number $$$i$$$ consists of $$$b_i$$$ independent towers, each of which currently contains $$$a_i$$$ units of water. The water level in each tower increases by $$$1$$$ unit every second. After exactly $$$t_i$$$ seconds, a water discharge into the sewer system occurs in all towers of subsystem $$$i$$$, meaning that the water level in each tower becomes $$$0$$$ and stops increasing.
Shortly before the capture of the Riddler, he booby-trapped all the towers in each of the $$$n$$$ subsystems. After an explosion of any tower, all the water that was in the tower at that moment spills onto the city streets, and the supply of new water stops. Thus, if tower $$$i$$$ of subsystem $$$i$$$ is exploded at time $$$t \lt t_i$$$, $$$a_i + t$$$ units of water will spill onto the streets of the city. However, the explosion of one tower in a subsystem does not affect the other towers in that subsystem.
The Riddler has remote control devices to detonate each tower in the city. Every second, he can choose to detonate no more than $$$k$$$ (possibly zero) water towers. The villain wants to choose the order of detonations in such a way that the maximum amount of water flows onto the city streets (the water that flows as a result of the water discharge does not count).
Batman is concerned about the actions of his enemy, so he wants to know the maximum total amount of water that can end up on the city streets.
The first line of input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leqslant n \leqslant 10^5$$$, $$$1 \leqslant k \leqslant 10^9$$$) separated by a space - the number of subsystems of water towers in the city and the maximum number of towers that can be exploded in one second.
The next $$$n$$$ lines list the descriptions of the subsystems, the $$$i$$$-th line contains three integers separated by a space - $$$t_i$$$, $$$a_i$$$, and $$$b_i$$$ - the second when the water is discharged, the initial water level in the towers of the $$$i$$$-th subsystem, and the number of towers in the subsystem ($$$1 \leqslant t_i, b_i \leqslant 10^9$$$, $$$1 \leqslant a_i \leqslant 10^4$$$). It is guaranteed that the sum of $$$b_i$$$ for all $$$i$$$ does not exceed $$$10^9$$$.
Output a single integer - the maximum amount of water that can be on the streets of the city.
Points for each subtask are awarded only if all tests of this subtask and the necessary subtasks, as well as the tests from the statement, are passed successfully.
| Subtask | Points | Additional Constraints | Required Subtasks | Verification Information |
| 1 | 10 | the total number of towers $$$\leqslant 5$$$; $$$t_i \leqslant 5$$$ for all $$$i$$$; $$$k = 1$$$ | – | full |
| 2 | 15 | $$$k = 1$$$; $$$b_i = 1$$$ for all $$$i$$$; all $$$t_i$$$ are different | – | full |
| 3 | 10 | all $$$t_i$$$ are equal | – | full |
| 4 | 20 | $$$b_i = 1$$$ for all $$$i$$$ | 2 | full |
| 5 | 20 | $$$t_i \leqslant 10^5$$$ for all $$$i$$$ | 1 | first error |
| 6 | 25 | No additional constraints | 1 – 5 | first error |
3 2 10 3 1 2 2 1 4 1 1
19
3 1 10 3 7 2 2 3 4 1 1
69
In the first test case, there is one tower in each subsystem. The tower from the first subsystem can be detonated at the ninth second, yielding $$$3 + 9 = 12$$$ units of water; the tower from the second subsystem can be detonated at the first second, yielding $$$2 + 1 = 3$$$ units of water; the tower from the third subsystem can be detonated at the third second, yielding $$$1 + 3 = 4$$$ units of water. In total, we will obtain $$$12 + 3 + 4 = 19$$$ units of water. Note that we have obtained the maximum possible amount of water from each tower, so the answer is maximum.
In the second example, one tower from the second subsystem should be detonated at the first second, and the rest will be guaranteed to be flushed down the drain. The tower from the third subsystem can be detonated at the second or third second, but it is impossible to detonate all 7 towers from the first subsystem between the fourth and ninth seconds. Therefore, if we detonate the tower from the third subsystem at the third second, we should detonate one tower from the first subsystem at the second second. In both cases, the answer will be the same and equal to $$$((2 + 1)) + ((1 + 2)) + ((3 + 3) + (3 + 4) + \ldots + (3 + 9)) = 69$$$.
| Name |
|---|