Botas de nieve#10409
En la granja es invierno, ¡así que hay nieve! El camino desde la casa de la granja hasta el establo consta de baldosas, numeradas por conveniencia del al , y la baldosa está cubierta por una capa de nieve de profundidad f_i pies.
El granjero John comienza su camino en la baldosa y debe llegar a la baldosa para despertar a las vacas. La baldosa está bajo el techo de la casa de la granja, y la baldosa está bajo el techo del establo, por lo que en esas baldosas no hay nieve. Pero para pisar cualquier otra baldosa, ¡el granjero John necesita ponerse botas!
En su mochila para el mal tiempo, el granjero John tiene pares de botas, numerados del al . Unos pares son más resistentes que otros, mientras que otros le permiten desplazarse con más agilidad. En concreto, el par le permite al granjero John pisar nieve de una profundidad de hasta s_i pies y avanzar no más de d_i baldosas en un solo paso.
Desafortunadamente, las botas están guardadas de tal forma que en cualquier momento el granjero John solo tiene acceso al par de arriba del todo. Por eso, en cualquier momento el granjero John puede o bien ponerse el par de botas de arriba (desechando el par que lleva puesto actualmente), o bien desechar el par de botas de arriba (haciendo accesible el siguiente par).
El granjero John solo puede cambiarse de botas estando de pie sobre una baldosa. Si en esa baldosa hay una capa de nieve de profundidad pies, entonces tanto las botas que se quita COMO las botas que se pone deben soportar una profundidad de nieve de al menos pies. Los pares intermedios de botas que desecha sin llegar a ponérselos no están obligados a cumplir esta restricción.
Ayuda al granjero John a minimizar sus pérdidas: determina el número mínimo de pares de botas que tendrá que desechar para llegar al establo. Inicialmente, el granjero John está descalzo.
En la primera línea se dan dos números enteros y b~(2 \le n, b \le 250). En la segunda línea se dan números enteros f_1, f_2, \ldots, f_n~(0 \le f_i \le 10^9), donde f_i es la profundidad de la nieve en la baldosa . Se garantiza que f_1 = f_n = 0.
Cada una de las siguientes líneas contiene dos números enteros. La línea (i + 2)-ésima contiene los números s_i y d_i~(0 \le s_i \le 10^9, 1 \le d_i \le n - 1) — respectivamente, la profundidad máxima de nieve en la que se puede pisar con el par , y la longitud máxima de paso con el par .
Las botas se enumeran de arriba hacia abajo: el par es el que está más arriba en la mochila del granjero John, el par es el siguiente, y así sucesivamente.
Muestra un único número entero: el número mínimo de pares de botas que el granjero John tendrá que desechar. Se garantiza que el granjero John puede llegar al establo.
Ejemplo 1