Problem F
Sanitære faciliteter

Det er tid til at bygge nye toiletter til din bodega. Toiletter er dyre, så du ønsker at bygge så få som muligt men stadig sikre, at hver gæst har adgang til et ledigt toilet uden at skulle stå i kø. Ved hjælp af kasserede plastikkrus har du indsamlet biometriske data for hver af dine $n$ gæster i løbet af de sidste par uger.

En gæst drikker i $b$ sekunder, indtil blæren er fuld. Derefter besøger gæsten et ledigt toilet, tilbringer $d$ sekunder der, og begynder så straks at drikke igen. Denne proces fortsætter i $t$ sekunder, indtil bodegaen lukker. På dette tidspunkt må ingen længere gå på toilet.

Alle gæster begynder at drikke samtidig. Hvert toilet kan kun rumme én gæst ad gangen, og takket være den kønsneutrale toiletpolitik, som utvivlsomt vil gøre underværker for bodegaens ESG-score, kan hver gæst bruge ethvert toilet. På vej ind eller ud af toiletterne passerer gæsterne hinanden øjeblikkeligt og uden akavethed.

Input

• En linje med antallet $n\in \{1,\dots ,10000\}$ af gæster og lukketiden $t\in \{1,\dots ,500000\}$.

• $n$ linjer, hvor den $i$te linje indeholder blærekapaciteten $b_i\in \{1000,\dots ,7200\}$ og tømningsvarigheden $d_i\in \{100,\dots ,1800\}$ for den $i$te gæst.

Output

Det minimalt nødvendige antal toiletter.

2 4000
1000 500
1500 1000

1

2 4001
1000 500
1500 1000

2

1 1000
1000 100

0