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 ai pies de profundidad, y le permite a GJ moverse a lo más di 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 bota 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~ ~(2 \leq N,B \leq 250)~.

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~ ~( 0 \leq f_i \leq 109 )~. Se garantiza que ~f_1 = f_N = 0~.

Cada una de las siguientes ~B~ líneas continen dos enteros separados pro espacio. El primer enter en la línea ~i+2~ es si, la profundidad máxima de niece en sue 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 el para ~i~. Se garantiza que ~(0 \leq s_i \leq 109 )~ y ~(1 \leq d_i \leq N-1)~. Las botas están descritas en orden 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 mínimo número de botas que el Granjero Juan necesita descartar. Se garantiza que será posible que GJ llegue al establo.

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