RoAlgo Contest #9 | Larry the Lizard

Task

Larry the lazy lizard is taking a very hard Physics class in school. In this class, there is no homework, only tests! He also, being very lazy, wants to study as little as possible for his tests.

He has $N$ tests to take in this class. For each tests, you are given two values: $a_i$ and $b_i$. $a_i$ is the score he would receive if he studies, and $b_i$ is the score he would receive if he chooses not to study. Note that he can either study or not study, there is no in between.

His teacher has also has one conditional: he will only add up the scores of some $N - 1$ tests to get their final score! The teacher will randomly remove one test from the total score, but will tell Larry before all the tests are taken.

Note that the total score is calculated by sum of all his tests (unlike traditional schooling, their total score can get very high, not just out of $100$).

Given these conditions, please output the minimum amount of tests that Larry should study for to ensure that he gets a score of at least $Q$, no matter what happens ($Q$ is the cutoff for an A in his class), or output $-1$ if it is not possible no matter how much he studies. You must output the answer for each of the potential tests that the teacher removes (i.e output $n$ integers, where the $i^{\text{th}}$ integer represents the minimum number of tests to study for given that the teacher removes the $i^{\text{th}}$ test).

Input data

The first line contains two space separated integers, $N$ and $Q$. The next $N$ lines contain three integers, with the $i^{\text{th}}$ line containing the space separated integers $a_i$ and $b_i$, representing the scores after and before studying for that respective test.

Output data

Output $N$ lines, with the $i^{\text{th}}$ line containing the minimum amount of tests to study for given that the teacher will remove the $i^{\text{th}}$ test score, to get a total score of at least $Q$, or $-1$ if it's not possible.

Constraints and clarifications

• $1 \leq N \leq 10^5$;
• $1 \leq Q \leq 10^8$;
• $1 \leq b_i \leq a_i \leq 10^4$;

Example

stdin

3 5
5 0
3 2
2 1

stdout

2
1
1