Seongssipdang Meal Kit

Time limit2sMemory limit1024 MB

Summary

Given N ingredients with spoilage rates, expiration days, and removable flags, find the latest day x such that after removing at most K non-important ingredients the total bacteria count stays at most G.

Level: Medium7 of 10
Topics: Binary search, Greedy, Sorting, Implementation
Solved: No attempts yet

Problem

Seongssipdang, the bakery that Instagram bread lovers keep coming back to, has used the know-how Suhyeon has built up over the years to branch out into the meal kit business. Now you can enjoy the taste of Seongssipdang at home.

Hanbyeol, a bread lover who would never miss this news, ran straight to Seongssipdang and bought a meal kit. But Hanbyeol was busy solving problems and forgot to eat the meal kit before its expiration date. Holding back tears, Hanbyeol opened the package to throw the meal kit away, and at that moment discovered that each ingredient has a different expiration date. Because a meal kit's expiration date is determined by the earliest expiration date among all its ingredients, some ingredients whose expiration dates had not yet passed were still left.

A meal kit contains $N$ ingredients. The $i$ -th ingredient has an expiration date of $L_i$ days after the meal kit is purchased and a spoilage rate of $S_i$ . At $x$ days after purchase, the number of bacteria in the $i$ -th ingredient is

$S_i \times \max\left( 1, x-L_i \right)$

individuals. Here, $x$ is an integer.

If the sum of the numbers of bacteria in all ingredients is at most $G$ individuals, the meal kit can be eaten without worry. Hanbyeol, who wants very much to try the meal kit, decided to remove up to $K$ ingredients that are not important, and if the number of bacteria becomes at most $G$ individuals, to just eat it.

How many days after buying the meal kit can Hanbyeol eat it?

Input

The first line gives $N, G, K$ separated by spaces.

From the second line, among the $N$ lines, the $i$ -th line gives the information for the $i$ -th ingredient: the spoilage rate $S_i$ , the expiration date $L_i$ , and a number $O_i$ indicating whether it is an important ingredient. $O_i$ is $0$ or $1$ , and $O_i=1$ means the ingredient is not important and can be removed.

Output

When up to $K$ ingredients that are not important are removed, output how many days after purchase the meal kit can be eaten.

Constraints

$1 \le N \le 200\,000$
$1 \le G \le 10^9$
$0 \le K < N$
$1 \le S_i \le 10^9$
$1 \le L_i \le 10^9$
$O_i \in \left\{0,1\right\}$
The sum of $S_i$ over all ingredients does not exceed $G$ . ( $\sum_{1 \le i \le n} S_i \le G$ )
All numbers given as input are integers.

Examples3

Example 1
Input
```
4 36 0
2 14 1
3 8 1
5 12 1
7 10 0
```
Expected output
```
12
```
Example 2
Input
```
4 36 1
2 14 1
3 8 1
5 12 1
7 10 0
```
Expected output
```
13
```
Example 3
Input
```
4 36 2
2 14 1
3 8 1
5 12 1
7 10 0
```
Expected output
```
14
```