Es ist Winter auf dem Bauernhof, und das bedeutet Schnee! Auf dem Weg vom Haus zur Scheune liegen $N$ Platten, nummeriert $1 \dots N$. Platte $i$ ist von $f_i$ Fuß Schnee bedeckt.

Farmer John beginnt auf Platte $1$ und muss Platte $N$ erreichen, um die Kühe zu wecken. Platte $1$ liegt unter dem Hausdach und Platte $N$ unter dem Scheunendach, weshalb beide schneefrei sind. Für die anderen Platten braucht er Stiefel!

In seinem Schlechtwetterrucksack sind $B$ Stiefelpaare, nummeriert $1 \dots B$. Manche sind robuster, andere beweglicher. Paar $i$ erlaubt es, in höchstens $s_i$ Fuß tiefen Schnee zu treten und pro Schritt höchstens $d_i$ Platten vorwärtszugehen.

Leider ist stets nur das oberste Paar zugänglich. Er kann es jederzeit anziehen und das bisherige Paar wegwerfen, oder das oberste Paar wegwerfen, sodass das nächste zugänglich wird.

Stiefel wechseln darf er nur auf einer Platte. Liegen dort $f$ Fuß Schnee, müssen sowohl das ausgezogene ALS AUCH das angezogene Paar mindestens $f$ Fuß Schnee aushalten. Zwischenliegende Paare, die er ohne Anziehen wegwirft, müssen diese Bedingung nicht erfüllen.

Bestimme zur Verringerung der Verschwendung die minimale Anzahl wegzuwerfender Paare, um die Scheune zu erreichen. Anfangs trägt Farmer John keine Stiefel.

Eingabe

Die erste Zeile enthält die durch ein Leerzeichen getrennten ganzen Zahlen $N$ und $B$ ($2 \leq N,B \leq 250$).

Die zweite Zeile enthält $N$ durch Leerzeichen getrennte ganze Zahlen. Die Zahl an Position $i$ ist $f_i$, die Schneetiefe auf Platte $i$ ($0 \leq f_i \leq 10^9$). Es gilt garantiert $f_1 = f_N = 0$.

Die nächsten $B$ Zeilen enthalten je zwei ganze Zahlen, getrennt durch ein Leerzeichen. Die erste in Zeile $i+2$ ist $s_i$, die maximale Schneetiefe für Paar $i$. Die zweite in Zeile $i+2$ ist $d_i$, die maximale Schrittlänge für Paar $i$. Es gilt garantiert $0 \leq s_i \leq 10^9$ und $1 \leq d_i \leq N-1$.

Die Paare sind von oben nach unten beschrieben, also liegt Paar $1$ ganz oben im Rucksack, und so weiter.

Ausgabe

Gib eine ganze Zahl aus: die minimale Anzahl wegzuwerfender Stiefelpaare. Die Scheune kann garantiert erreicht werden.

Beispiele

Eingabe 1

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

Ausgabe 1

2

Aufgabenautoren: Brian Dean und Dhruv Rohatgi