Picking flowers - MarisaOJ: Marisa Online Judge

Picking flowers

Time limit: 1000 ms
Memory limit: 256 MB
On a field of flowers lies a coordinate axis with $n$ blooming flowers. The $i^{th}$ flower is located at position $x_i$ and takes $t_i$ minutes to pick. These flowers will wither when it starts raining. It is known that it will rain after $m$ minutes. Marisa starts at position $0$. Each minute, she can move one unit of distance. How many flowers can Marisa pick optimally? She can choose to skip picking certain flowers. ### Input - The first line contains two integers $n$ and $m$. - The next $n$ lines each contain two integers $x_i$ and $t_i$. ### Output - Output a single integer representing the maximum number of flowers Marisa can pick. ### Constraints - $1 \le n \le 2 \times 10^5$. - $1 \le m, x_i, t_i \le 10^9$. It is guaranteed that the values of $x_i$ are distinct for all $i$'s. ### Example Input: ``` 2 12 1 1000 6 6 ``` Output: ``` 1 ```