A. Coffee Cocktail
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sometimes the deadline sneaks up unnoticed and in order to finish a task on time you have to work all night. To stay awake it's easiest to drink coffee.

Programmer Lev from VK usually manages to complete all the assigned tasks in advance but this time he procrastinated the last task for too long and plans to finish it tonight. In order to stay alert he needs at least $$$x$$$ caffeine. To achieve this he plans to assemble a set of coffee snacks that are always available in the office.

There are a total of $$$n$$$ snacks, each with a mass of $$$m_i$$$ and a caffeine content of $$$k_i \%$$$. Additionally, each snack has a type (drink, cookie, chocolate bar, etc.) characterized by the integer $$$t_i$$$.

Mixing snacks of different types is not ideal, so Lev wants to use as few different types of snacks as possible. Help him choose a set of snacks with a total caffeine mass of at least $$$x$$$, while minimizing the number of different types of snacks.

Input

The first line of input contains three integers $$$n$$$, $$$q$$$, and $$$x$$$ separated by a space, representing the number of different snacks, the number of snack types, and the required caffeine mass, respectively ($$$1 \le q \le n \le 2 \cdot 10^5$$$; $$$1 \le x \le 10^9$$$).

Each of the following lines contains three integers $$$t_i$$$, $$$m_i$$$, and $$$k_i$$$ separated by a space, representing the type, total mass, and percentage caffeine content of the $$$i$$$-th snack ($$$1 \le t_i \le q$$$; $$$1 \le m_i \le 10^9$$$; $$$0 \le k_i \le 100$$$).

Output

Output a single integer representing the minimum number of snack types required to achieve $$$x$$$ caffeine. If it is impossible to achieve $$$x$$$ caffeine even by taking all the snacks, output "-1" (without quotes).

Scoring

Points for each subtask are awarded only if all the tests of that subtask and the required subtasks are successfully passed.

SubtaskPointsConstraintsRequired Subtasks
0–examples from the statement
112$$$q = 1$$$
216$$$k_i = 100$$$, $$$t_i \ne t_j$$$, $$$m_i = m_j$$$ for all $$$i$$$, $$$j$$$
318$$$t_i \ne t_j$$$, $$$k_i = k_j$$$ for all $$$i$$$, $$$j$$$2
417$$$t_i \ne t_j$$$ for all $$$i$$$, $$$j$$$2, 3
517$$$k_i = k_j$$$ for all $$$i, j$$$2, 3
620none0 – 5
Examples
Input
4 3 10
1 4 25
2 5 100
2 4 100
3 1 10
Output
2
Input
5 4 3
1 4 50
1 5 20
2 2 50
2 2 25
4 2 100
Output
1