Снігові черевики
На фермі настала зима, і це означає багато снігу! Є n плиток на доріжці від ферми до амбару, пронумерованих послідовно від 1 до n, де плитка номер i покрита f[i] футами снігу.
Фермер Джон починає свій шлях з плитки 1 і повинен дістатися до плитки n, щоб розбудити своїх корів. Плитка 1 захищена дахом ферми, а плитка n — дахом амбару, тому на них немає снігу. Але для того, щоб пройти по інших плитках, Фермер Джон повинен носити чоботи.
У Фермера Джона є b пар чобіт, пронумерованих від 1 до b. Деякі з них важкі, а деякі легші. Зокрема, пара i дозволяє Фермеру Джону ходити по снігу глибиною не більше 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 — найверхня пара в пакеті чобіт і так далі.
Вихідні дані
Вивід повинен складатися з одного цілого числа, яке вказує мінімальну кількість пар чобіт, які Фермер Джон повинен відставити. Гарантується, що Фермер Джон завжди може дійти до амбару.