Na farmie jest zima, a więc śnieg! Ścieżka od domu do stodoły ma $N$ płytek ponumerowanych $1 \dots N$, a płytkę $i$ pokrywa śnieg o głębokości $f_i$ stóp.

Farmer John zaczyna na płytce $1$ i musi dotrzeć do płytki $N$, aby obudzić krowy. Płytkę $1$ osłania dach domu, a płytkę $N$ dach stodoły, więc nie ma na nich śniegu. Aby stawać na pozostałych, potrzebuje butów!

W plecaku na złą pogodę ma $B$ par butów, ponumerowanych $1 \dots B$. Niektóre są bardziej wytrzymałe, inne bardziej zwinne. Para $i$ pozwala stawać w śniegu o głębokości najwyżej $s_i$ stóp i iść do przodu o najwyżej $d_i$ płytek na krok.

Niestety zawsze dostępna jest tylko para na wierzchu. Może ją założyć, wyrzucając starą parę, albo wyrzucić parę z wierzchu, udostępniając następną.

Buty można zmieniać tylko stojąc na płytce. Jeśli ma ona $f$ stóp śniegu, zarówno zdejmowana, JAK I zakładana para muszą wytrzymać co najmniej $f$ stóp śniegu. Pary pośrednie wyrzucane bez zakładania nie muszą spełniać tego ograniczenia.

Aby zmniejszyć marnotrawstwo, wyznacz minimalną liczbę par, które trzeba wyrzucić, aby dojść do stodoły. Początkowo Farmer John nie ma założonych butów.

Wejście

Pierwszy wiersz zawiera liczby całkowite $N$ i $B$ oddzielone spacją ($2 \leq N,B \leq 250$).

Drugi wiersz zawiera $N$ liczb całkowitych oddzielonych spacjami. Liczba na pozycji $i$ to $f_i$, głębokość śniegu na płytce $i$ ($0 \leq f_i \leq 10^9$). Gwarantowane jest $f_1 = f_N = 0$.

Kolejne $B$ wierszy zawiera po dwie liczby całkowite oddzielone spacją. Pierwsza w wierszu $i+2$ to $s_i$, maksymalna głębokość śniegu dla pary $i$. Druga w wierszu $i+2$ to $d_i$, maksymalna długość kroku dla pary $i$. Gwarantowane jest $0 \leq s_i \leq 10^9$ oraz $1 \leq d_i \leq N-1$.

Pary opisane są od góry do dołu, więc para $1$ jest na wierzchu plecaka, i tak dalej.

Wyjście

Wypisz jedną liczbę całkowitą: minimalną liczbę par do wyrzucenia. Gwarantowane jest, że można dotrzeć do stodoły.

Przykład

Wejście 1

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

Wyjście 1

2

Autorzy zadania: Brian Dean i Dhruv Rohatgi