¡Es invierno en la granja y eso significa nieve! Hay $N$ baldosas en el camino de la casa al granero, numeradas $1 \dots N$, y la baldosa $i$ está cubierta por $f_i$ pies de nieve.
Farmer John empieza en la baldosa $1$ y debe llegar a la $N$ para despertar a las vacas. La baldosa $1$ está protegida por el techo de la casa y la $N$ por el del granero, así que ninguna tiene nieve. ¡Para pisar las demás necesita botas!
En su mochila para el mal tiempo tiene $B$ pares de botas, numerados $1 \dots B$. Unos son más resistentes y otros más ágiles. El par $i$ permite pisar nieve de hasta $s_i$ pies de profundidad y avanzar hasta $d_i$ baldosas por paso.
Por desgracia, solo puede acceder al par de arriba. En cualquier momento puede ponérselo, desechando el anterior, o desechar el par superior para acceder al siguiente.
Solo puede cambiarse de botas estando sobre una baldosa. Si tiene $f$ pies de nieve, tanto el par que se quita COMO el que se pone deben soportar al menos $f$ pies de nieve. Los pares intermedios que desecha sin ponérselos no necesitan cumplir esta restricción.
Para minimizar el desperdicio, determina el mínimo número de pares que debe desechar para llegar al granero. Al principio no lleva botas.
Entrada
La primera línea contiene los enteros $N$ y $B$ separados por un espacio ($2 \leq N,B \leq 250$).
La segunda contiene $N$ enteros separados por espacios. El entero $i$ es $f_i$, la profundidad de nieve en la baldosa $i$ ($0 \leq f_i \leq 10^9$). Se garantiza $f_1 = f_N = 0$.
Las siguientes $B$ líneas contienen dos enteros separados por un espacio. El primero en la línea $i+2$ es $s_i$, la máxima profundidad de nieve para el par $i$. El segundo en la línea $i+2$ es $d_i$, el máximo tamaño de paso para el par $i$. Se garantiza $0 \leq s_i \leq 10^9$ y $1 \leq d_i \leq N-1$.
Los pares se describen de arriba abajo, por lo que el par $1$ es el superior de la mochila, y así sucesivamente.
Salida
Imprime un entero: el mínimo número de pares que debe desechar. Se garantiza que puede llegar al granero.
Ejemplos
Entrada 1
10 4 0 2 8 3 6 7 5 1 4 0 2 3 4 2 3 4 7 1
Salida 1
2
Autores: Brian Dean y Dhruv Rohatgi