[USACO18FEB] Snow Boots S

到冬天了，这意味着下雪了！从农舍到牛棚的路上有$N$块地砖，方便起见编号为$1 \dots N$，第$i$块地砖上积了$f_i$英尺的雪。 Farmer John从$1$号地砖出发，他必须到达$N$号地砖才能叫醒奶牛们。$1$号地砖在农舍的屋檐下，$N$号地砖在牛棚的屋檐下，所以这两块地砖都没有积雪。但是在其他的地砖上，Farmer John只能穿靴子了！ 在Farmer John的恶劣天气应急背包中，总共有$B$双靴子，编号为$1 \dots B$。其中某些比另一些结实，某些比另一些轻便。具体地说，第$i$双靴子能够让FJ在至多$s_i$英尺深的积雪中行走，能够让FJ每步至多前进$d_i$。 不幸的是，这些靴子都套在一起，使得Farmer John在任何时刻只能拿到最上面的那一双。所以在任何时刻，Farmer John可以穿上最上面的一双靴子（抛弃原来穿着的那双），或是丢弃最上面的那一双靴子（使得可以拿到下面那一双）。 Farmer John只有在地砖上的时候才能换靴子。如果这块地砖的积雪有$f$英尺，他换下来的靴子和他换上的那双靴子都要能够承受至少$f$英尺的积雪。中间没有穿就丢弃的靴子无需满足这一限制。 帮助Farmer John最小化他的消耗，确定他最少需要丢弃的靴子的双数。你可以假设Farmer John在开始的时候没有穿靴子。 输入格式（文件名：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$。 输出格式（文件名：snowboots.out）： 输出包含一个整数，为Farmer John需要丢弃的靴子的最小双数。输入保证Farmer John能够到达牛棚。

It's winter on the farm, and that means snow! There are $N$ tiles on the path from the farmhouse to the barn, conveniently numbered $1 \dots N$, and tile $i$ is covered in $f_i$ feet of snow. Farmer John starts off on tile $1$ and must reach tile $N$ to wake up the cows. Tile $1$ is sheltered by the farmhouse roof, and tile $N$ is sheltered by the barn roof, so neither of these tiles has any snow. But to step on the other tiles, Farmer John needs to wear boots! In his foul-weather backpack, Farmer John has $B$ pairs of boots, numbered $1 \dots B$. Some pairs are more heavy-duty than others, and some pairs are more agile than others. In particular, pair $i$ lets FJ step in snow at most $s_i$ feet deep, and lets FJ move at most $d_i$ forward in each step. Unfortunately, the boots are packed in such a way that Farmer John can only access the topmost pair at any given time. So at any time, Farmer John can either put on the topmost pair of boots (discarding his old pair) or discard the topmost pair of boots (making a new pair of boots accessible). Farmer John can only change boots while standing on a tile. If that tile has $f$ feet of snow, both the boots he takes off AND the boots he puts on must be able to withstand at least $f$ feet of snow. Intermediate pairs of boots which he discards without wearing do not need to satisfy this restriction. Help Farmer John minimize waste, by determining the minimum number of pairs of boots he needs to discard in order to reach the barn. You may assume that Farmer John is initially not wearing any boots.

The first line contains two space-separated integers $N$ and $B$ ($2 \leq N,B \leq 250$). The second line contains $N$ space-separated integers. The $i$th integer is $f_i$, giving the depth of snow on tile $i$ ($0 \leq f_i \leq 10^9$). It's guaranteed that $f_1 = f_N = 0$. The next $B$ lines contain two space-separated integers each. The first integer on line $i+2$ is $s_i$, the maximum depth of snow in which pair $i$ can step. The second integer on line $i+2$ is $d_i$, the maximum step size for pair $i$. It's guaranteed that $0 \leq s_i \leq 10^9$ and $1 \leq d_i \leq N-1$. The boots are described in top-to-bottom order, so pair $1$ is the topmost pair in FJ's backpack, and so forth.

The output should consist of a single integer, giving the minimum number of boots Farmer John needs to discard. It's guaranteed that it will be possible for FJ to make it to the barn.

10 4
0 2 8 3 6 7 5 1 4 0
2 3
4 2
3 4
7 1

2

Problem credits: Brian Dean and Dhruv Rohatgi