È inverno nella fattoria, e quindi nevica! Sul percorso dalla casa al fienile ci sono $N$ mattonelle numerate $1 \dots N$, e la mattonella $i$ ha $f_i$ piedi di neve.
Farmer John parte dalla mattonella $1$ e deve raggiungere la $N$ per svegliare le mucche. La mattonella $1$ è riparata dal tetto della casa e la $N$ da quello del fienile, quindi nessuna ha neve. Per calpestare le altre servono stivali!
Nel suo zaino per il maltempo ci sono $B$ paia di stivali numerate $1 \dots B$. Alcune sono più resistenti, altre più agili. Il paio $i$ permette di calpestare neve profonda al massimo $s_i$ piedi e avanzare al massimo di $d_i$ mattonelle per passo.
Purtroppo, solo il paio in cima è accessibile. In ogni momento può indossarlo, scartando il vecchio paio, oppure scartare il paio in cima per accedere al successivo.
Può cambiare stivali solo su una mattonella. Se vi sono $f$ piedi di neve, sia il paio tolto SIA quello indossato devono sopportare almeno $f$ piedi di neve. Le paia intermedie scartati senza indossarli non devono soddisfare questo vincolo.
Per ridurre gli sprechi, determina il minimo numero di paia da scartare per raggiungere il fienile. All’inizio Farmer John non indossa stivali.
Input
La prima riga contiene gli interi $N$ e $B$ separati da uno spazio ($2 \leq N,B \leq 250$).
La seconda contiene $N$ interi separati da spazi. L’intero in posizione $i$ è $f_i$, la profondità della neve sulla mattonella $i$ ($0 \leq f_i \leq 10^9$). È garantito che $f_1 = f_N = 0$.
Le successive $B$ righe contengono due interi separati da uno spazio. Il primo nella riga $i+2$ è $s_i$, la massima profondità della neve per il paio $i$. Il secondo nella riga $i+2$ è $d_i$, la massima lunghezza del passo per il paio $i$. È garantito che $0 \leq s_i \leq 10^9$ e $1 \leq d_i \leq N-1$.
Le paia sono descritte dall’alto verso il basso: il paio $1$ è in cima allo zaino, e così via.
Output
Stampa un intero: il minimo numero di paia da scartare. È garantito che può raggiungere il fienile.
Esempi
Input 1
10 4 0 2 8 3 6 7 5 1 4 0 2 3 4 2 3 4 7 1
Output 1
2
Autori: Brian Dean e Dhruv Rohatgi