Es invierno en la granja, y eso quiere decir nieve. Hay ~N~ baldosas en el camino de la granja al establo, convenientemente numeradas ~1...N~, y la baldosa ~i~ está cubierta por ~f_i~ pies de nieve. El Granjero Juan comienza en la baldosa 1 y debe llegar a la baldosa ~N~ para despertar a las vacas. La baldosa 1 está cubierta por el techo de la granja, y la baldosa ~N~ está cubierta por el techo del establo, entonces ninguna de estas baldosas tiene nieve. Pero para las otras baldosas, el Granjero Juan necesita usar botas. En su mochila para clima malo, el Granjero Juan tiene ~B~ pares de botas, numeradas ~1...B~. Algunos pares son más de trabajo pesado que otras, y algunos son más ágiles que otros. En particular, el par ~i~ le deja a GJ pararse en nieve de a lo más ~a_i~ pies de profundidad, y le permite a GJ moverse a lo más ~d_i~ pies adelante en cada paso.

Desafortunadamente, las botas están empacadas de tal manera que el Granjero Juan puede acceder únicamente al par de más arriba cada vez. Por lo tanto, en cualquier momento, el Granjero Juan puede ponerse las botas de más arriba (descartando el viejo par) o descartar el par de más arriba (haciendo accesible un nuevo par de botas). El Granjero Juan puede cambiarse de botas únicamente cuando está en una baldosa. Si la baldosa tiene ~f_i~ pies de nieve, ambas botas que el se quita Y las botas que se pone deben ser capaces de mantenerse en al menos ~f_i~ pies de nieve. Los pares intermedios que el descarta sin usarlos no necesitan satisfacer esta restricción. Ayude al Granjero Juan a minimizar el gasto, determinando el número mínimo de pares de botas que él necesita descartar con el propósito de llegar al establo. Usted puede asumir que el Granjero Juan inicialmente no tiene botas.

Entrada

• La primera línea contiene dos enteros separados por espacio ~N~ y ~B~.
• La segunda línea contiene ~N~ enteros separados por espacios. El entero i-ésimo es ~f_i~, dando la profundidad de nieve en la baldosa ~i~. Se garantiza que ~f_1=f_N=0~.
• Cada una de las siguientes ~B~ líneas continen dos enteros separados por espacio. El primer entero en la línea ~i+2~ es ~s_i~, la profundidad máxima de nieve en el par ~i~ puede pararse. El segundo entero en la línea ~i+2~ es ~d_i~, el tamaño máximo de paso para ~i~.

Las botas están descritas en orden de arriba hacia abajo, entonces el par 1 es el par de más arriba en la mochila de GJ, y así sucesivamente.

Salida

La salida debe consistir de un solo entero, dando el número mínimo de botas que el Granjero Juan necesita descartar. Se garantiza que será posible que GJ llegue al establo.

Restricciones

• ~2 \leq N,B \leq 250~
• ~0 \leq f_i \leq 10^9~
• ~0 \leq s_i \leq 10^9~
• ~1 \leq d_i \leq N-1~

Ejemplo de Entrada

10 4
0 2 8 3 6 7 5 1 4 0
2 3
4 2
3 4
7 1

Ejemplo de Salida

2

USACO 2018 February Contest, Silver Problem 2. Snow Boots.