На ферме зима и значит много снега! Имеется \(N\) фрагментов на дорожке от фермы
к амбару, последовательно пронумерованных \(1 \dots N\), и фрагмент \(i\) покрыт
\(f_i\) футами снега.
Фермер Джон начинает с фрагмента \(1\) и должен достичь фрагмента \(N\), чтобы
разбудить своих коров. Фрагмент \(1\) защищён крышей фермы, а фрагмент \(N\)
- крышей амбара, поэтому на них нет снега. Но чтобы ходить по другим фрагментам
ФД должен носить ботинки.
У ФД есть \(B\) пар ботинок, пронумерованных \(1 \dots B\). Некоторые из них тяжёлые,
а некоторые полегче. В частности, пара \(i\) позволяет ФД ходить по снегу не более
\(s_i\) футов глубины и позволяет ФД продвигаться на расстояние \(d_i\) вперёд на
каждом шагу.
К несчастью, ботинки упакованы таким образом, что ФД может взять только самую
верхнюю пару в любой момент времени. Поэтому в любой момент времени ФД может
или положить наверх пару ботов (отказываясь от старых ботов) или снять верхнюю
пару ботов, делая новую пару доступной).
ФД может менять ботинки только когда стоит на фрагменте. Если он стоит на
фрагменте, то и те ботинки, которые он снимает, и те ботинки, которые он надевает,
должны быть выше снега, как минимум на \(f\) футов. Промежуточные пары ботинок,
которые он снимает из стопки ботинок не одевая, могут не удовлетворять этому
ограничению.
Помогите ФД минимизировать отбросы, определив минимальное количество пар
ботов, которые он должен снять из стопки не одевая, чтобы достичь амбара.
Вы можете считать, что изначально на ФД нет никаких ботинок.
ФОРМАТ ВВОДА (файл snowboots.in):
Первая строка ввода содержит два разделённых пробелом целых числа
\(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\) - самая верхняя
пара в пакете ботинок и т.д.
ФОРМАТ ВЫВОДА (файл snowboots.out):
Вывод должен состоять из одного целого числа, задающего минимальное количество
па ботинок, которые ФД должен отставить. Гарантируется, что ФД всегда может дойти
до амбара.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 4
0 2 8 3 6 7 5 1 4 0
2 3
4 2
3 4
7 1
|
2
|