На ферме зима, а значит, снег! На дорожке от дома до амбара $N$ плиток, пронумерованных $1 \dots N$. Плитка $i$ покрыта снегом глубиной $f_i$ футов.
Farmer John начинает на плитке $1$ и должен добраться до плитки $N$, чтобы разбудить коров. Плитка $1$ защищена крышей дома, а плитка $N$ — крышей амбара, поэтому на них нет снега. Чтобы наступать на остальные плитки, нужны ботинки!
В рюкзаке для непогоды у Farmer John есть $B$ пар ботинок с номерами $1 \dots B$. Одни пары прочнее, другие подвижнее. В частности, пара $i$ позволяет наступать в снег глубиной не более $s_i$ футов и двигаться вперёд не более чем на $d_i$ плиток за шаг.
К сожалению, из-за укладки в любой момент доступна только верхняя пара. Можно надеть её, выбросив старую, либо выбросить верхнюю пару, открыв доступ к следующей.
Менять ботинки можно только стоя на плитке. Если на ней снег глубиной $f$ футов, и снимаемая, и надеваемая пары должны выдерживать снег глубиной хотя бы $f$ футов. Промежуточные пары, выбрасываемые без надевания, не обязаны удовлетворять этому условию.
Помогите Farmer John уменьшить отходы: найдите минимальное число пар, которые нужно выбросить, чтобы добраться до амбара. Изначально на нём нет ботинок.
Входные данные
Первая строка содержит целые числа $N$ и $B$ через пробел ($2 \leq N,B \leq 250$).
Вторая строка содержит $N$ целых чисел через пробел. Число $i$ равно $f_i$, глубине снега на плитке $i$ ($0 \leq f_i \leq 10^9$). Гарантируется $f_1 = f_N = 0$.
Следующие $B$ строк содержат по два целых числа через пробел. Первое в строке $i+2$ — $s_i$, максимальная глубина снега для пары $i$; второе в строке $i+2$ — $d_i$, максимальная длина шага для пары $i$. Гарантируется $0 \leq s_i \leq 10^9$ и $1 \leq d_i \leq N-1$.
Пары описаны сверху вниз, поэтому пара $1$ находится наверху рюкзака, и так далее.
Выходные данные
Выведите одно целое число — минимальное число пар ботинок, которые нужно выбросить. Гарантируется, что Farmer John сможет добраться до амбара.
Примеры
Входные данные 1
10 4 0 2 8 3 6 7 5 1 4 0 2 3 4 2 3 4 7 1
Выходные данные 1
2
Авторы: Brian Dean и Dhruv Rohatgi