3034. [USACO Feb18 Silver]Snow Boots

【题目描述】

到冬天了，这意味着下雪了！从农舍到牛棚的路上有 $ N $ 块地砖，方便起见编号为 $1…N$，第 $i$ 块地砖上积了 $f_i$ 英尺的雪。

$Farmer$ $John$从 $1$ 号地砖出发，他必须到达 $N$ 号地砖才能叫醒奶牛们。$1$ 号地砖在农舍的屋檐下，$N$ 号地砖在牛棚的屋檐下，所以这两块地砖都没有积雪。但是在其他的地砖上，$Farmer$ $John$只能穿靴子了！

在$Farmer$ $John$的恶劣天气应急背包中，总共有 $B$ 双靴子，编号为 $1…B$。其中某些比另一些结实，某些比另一些轻便。具体地说，第 $i$ 双靴子能够让 $FJ$ 在至多 $s_i$ 英尺深的积雪中行走，能够让 $FJ$ 每步至多前进 $d_i$。

不幸的是，这些靴子都套在一起，使得$Farmer$ $John$在任何时刻只能拿到最上面的那一双。所以在任何时刻，$Farmer$ $John$可以穿上最上面的一双靴子（抛弃原来穿着的那双），或是丢弃最上面的那一双靴子（使得可以拿到下面那一双）。

$FJ$只有在地砖上的时候才能换靴子。如果这块地砖的积雪有 $f$ 英尺，他换下来的靴子和他换上的那双靴子都要能够承受至少 $f$ 英尺的积雪。中间没有穿就丢弃的靴子无需满足这一限制。

帮助$Farmer$ $John$最小化他的消耗，确定他最少需要丢弃的靴子的双数。你可以假设$Farmer$ $John$在开始的时候没有穿靴子。

【输入格式】

第一行包含两个空格分隔的整数 $N$ 和 $B（2≤N,B≤250）$。

第二行包含 $N$ 个空格分隔的整数。第 $i$ 个整数为 $f_i$，即 $i$ 号地砖的积雪深度$（0≤fi≤10^9）$。输入保证$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$。

【输出格式】

输出包含一个整数，为$Farmer$ $John$需要丢弃的靴子的最小双数。输入保证$Farmer$ $John$能够到达牛棚。

【样例输入】

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

【样例输出】

2

【来源】

USACO 2018 February Contest SILVER Problem 2

供题：Brian Dean，Dhruv Rohatgi