Los castores organizadores del Monotonically Increasing Tardiness Informatics Tournament (MITIT) necesitan reunirse regularmente para asegurar que el concurso se desarrolle sin problemas, pero a veces pierden la motivación.
Hay $N$ castores organizadores que tienen reuniones regularmente que duran exactamente $M$ minutos. El $i$-ésimo castor llega $t_i$ minutos tarde a la primera reunión. En cada reunión sucesiva, el castor $i$ llega $a_i$ minutos más tarde de lo que llegó a la reunión anterior. Imprima la primera reunión en la que todos llegan tan tarde que se pierden toda la reunión.
Se dice que un castor se ha perdido toda la reunión si llega al menos $M$ minutos tarde.
Entrada
La primera línea contiene dos enteros separados por espacios $N$ ($ 1 \le N \le 2\cdot 10^5$) y $M$ ($ 1 \le M \le 10^9$).
La $i$-ésima de las siguientes $N$ líneas contiene dos enteros $t_i$ ($0 \le t_i < M$) y $a_i$ ($1 \le a_i \le 10^9$).
Salida
Imprima una línea con la respuesta.
Ejemplos
Entrada
4 60 0 9 30 4 10 12 14 9
Salida
9
Nota
Para la primera reunión, el castor $1$ llega a tiempo, el castor $2$ llega $30$ minutos tarde, el castor $3$ llega $10$ minutos tarde y el castor $4$ llega $14$ minutos tarde. Para la reunión $9$, el castor $1$ llega $72$ minutos tarde, el castor $2$ llega $62$ minutos tarde, el castor $3$ llega $106$ minutos tarde y el castor $4$ llega $86$ minutos tarde. Esta es la primera reunión para la cual todos llegan al menos $60$ minutos tarde; para la reunión $8$, el castor $2$ llega $58$ minutos tarde.