Снігові чоботи#10409

Снігові чоботи

1 секунда

128 мегабайтів

Середня

На фермі зима, а отже — сніг! Доріжка від фермерського будинку до сараю складається з $n$ плиток, для зручності пронумерованих від $1$ до $n$ , і плитка $i$ вкрита шаром снігу глибиною $f_{i}$ f_i футів.

Фермер Джон починає шлях з плитки $1$ і повинен дістатися до плитки $n$ , щоб розбудити корів. Плитка $1$ знаходиться під дахом фермерського будинку, а плитка $n$ — під дахом сараю, тому на цих плитках снігу немає. Але щоб ступити на будь-яку іншу плитку, фермеру Джону потрібно одягнути чоботи!

У рюкзаку для негоди у фермера Джона лежать $b$ пар чобіт, пронумерованих від $1$ до $b$ . Одні пари міцніші за інші, а інші дозволяють пересуватися спритніше. А саме, пара $i$ дозволяє фермеру Джону ступати в сніг глибиною не більше $s_{i}$ s_i футів і просуватися вперед не більше ніж на $d_{i}$ d_i плиток за один крок.

На жаль, чоботи складені так, що в будь-який момент фермеру Джону доступна лише верхня пара. Тому в будь-який момент фермер Джон може або одягнути верхню пару чобіт (викинувши пару, яка зараз на ньому), або викинути верхню пару чобіт (зробивши доступною наступну пару).

Фермер Джон може міняти чоботи, лише стоячи на плитці. Якщо на цій плитці лежить шар снігу глибиною $f$ футів, то і чоботи, які він знімає, І чоботи, які він одягає, повинні витримувати сніг глибиною не менше $f$ футів. Проміжні пари чобіт, які він викидає, не одягаючи, цій умові задовольняти не зобов'язані.

Допоможіть фермеру Джону звести втрати до мінімуму: визначте мінімальну кількість пар чобіт, яку йому доведеться викинути, щоб дістатися до сараю. Спочатку фермер Джон не взутий.

Вхідні дані

У першому рядку задано два цілих числа $n$ і $b (2 \leq n, b \leq 250)$ b~(2 \le n, b \le 250). У другому рядку задано $n$ цілих чисел $f_{1}, f_{2}, \dots, f_{n} (0 \leq f_{i} \leq 1 0^{9})$ f_1, f_2, \ldots, f_n~(0 \le f_i \le 10^9), де $f_{i}$ f_i — глибина снігу на плитці $i$ . Гарантується, що $f_{1} = f_{n} = 0$ f_1 = f_n = 0.

Кожен з наступних $b$ рядків містить два цілих числа. $(i + 2)$ (i + 2)-й рядок містить числа $s_{i}$ s_i і $d_{i} (0 \leq s_{i} \leq 1 0^{9}, 1 \leq d_{i} \leq n - 1)$ d_i~(0 \le s_i \le 10^9, 1 \le d_i \le n - 1) — відповідно максимальну глибину снігу, в який можна ступати в парі $i$ , і максимальну довжину кроку в парі $i$ .

Чоботи перелічені зверху вниз: пара $1$ — найвища в рюкзаку фермера Джона, пара $2$ — наступна за нею, і так далі.

Вихідні дані

Виведіть одне ціле число — мінімальну кількість пар чобіт, яку фермеру Джону доведеться викинути. Гарантується, що фермер Джон може дістатися до сараю.

Приклади

Приклад 1