Снежные ботинки
На ферме зима и значит много снега! Имеется n плиток на дорожке от фермы к амбару, последовательно пронумерованных 1..n, плитка номер i покрыта f[i] футами снега.
Фермер Джон начинает с плитки 1 и должен достичь плитки n, чтобы разбудить своих коров. Плитка 1 защищена крышей фермы, а плитка n защищена крышей амбара, поэтому на них нет снега. Но чтобы ходить по другим плиткам, Фермер Джон должен носить ботинки.
У Фермера Джона имеется b пар ботинок, пронумерованных 1..b. Некоторые из них тяжёлые, а некоторые полегче. В частности, пара i позволяет Фермерe Джонe ходить по снегу не более s[i] футов глубины и позволяет продвигаться на расстояние d[i] вперёд на каждом шагу.
К несчастью, ботинки упакованы таким образом, что Фермер Джон может взять только самую верхнюю пару в любой момент времени. Поэтому в любой момент времени Фермер Джон может или положить наверх пару ботов (отказаться от старых ботов) или снять верхнюю пару ботов, делая новую пару доступной).
Фермер Джон может менять ботинки только когда стоит на плитке. Если он стоит на плитке, то и те ботинки, которые он снимает, и те ботинки, которые он надевает, должны быть выше снега, как минимум на f футов. Промежуточные пары ботинок, которые он снимает из стопки ботинок не одевая, могут не удовлетворять этому ограничению.
Помогите Фермеру Джону минимизировать отбросы, определив минимальное количество пар ботов, которые он должен снять из стопки не одевая, чтобы достичь амбара. Вы можете считать, что изначально на ФД нет никаких ботинок.
Входные данные
Первая строка ввода содержит два целых числа n и b (2 ≤ n, b ≤ 250).
Вторая строка содержит n целых чисел. i-ое число есть f[i] (0 ≤ f[i] ≤ 10^9), глубина снега на фрагменте i. Гарантируется, что f[1] = f[n] = 0.
Следующие b строк содержат по два целых числа. Первое целое число в строке i + 2 есть s[i] - максимальная глубина снега, в который может ступить пара i. Второе целое число в строке i + 2 есть d[i], максимальный размер шага для пары i. Гарантируется, что 0 ≤ s[i] ≤ 10^9 и 1 ≤ d[i] ≤ n − 1.
Ботинки описываются в порядке сверху-вниз, потому пара 1 - самая верхняя пара в пакете ботинок и т.д.
Выходные данные
Вывод должен состоять из одного целого числа, задающего минимальное количество па ботинок, которые ФД должен отставить. Гарантируется, что ФД всегда может дойти до амбара.