Problem F
Facilities

It is time to build new restrooms for your bar. Restrooms are expensive, so you want to build as few as possible while ensuring that every guest has access to an unoccupied restroom without having to stand in line. Using discarded plastic cups you have collected the biometric data of each of the $n$ guests over the past few weeks.

A guest drinks for $b$ seconds, until his or her bladder is full. The guest then visits an unoccupied restroom and spends $d$ seconds there, after which he or she immediately starts drinking again. This process continues for $t$ seconds, when the bar closes. At this point nobody is allowed to enter a restroom.

All guests start drinking at the same time. Every restroom admits at most one guest at a time, and thanks to the gender-neutral bathroom policy, which surely will do wonders for your bar’s ESG score, every guest can use every restroom. Guests pass each other on their way into or out of a stall instantaneously and without awkwardness.

Input

• One line with the number $n\in \{ 1,\ldots , 10000\} $ of guests and the closing time $t\in \{ 1,\ldots , 500\, 000\} $.

• $n$ lines, the $i$th of which contains the bladder capacity $b_i\in \{ 1000,\ldots , 7200\} $ and release duration $d_i\in \{ 100, \ldots , 1800\} $ of the $i$th guest.

Output

The minimum number of restrooms needed.

2 4000
1000 500
1500 1000

1

2 4001
1000 500
1500 1000

2

1 1000
1000 100

0