P4265 [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$ 双靴子允许 Farmer John 在最多 $s_i$ 英尺深的雪中行走，并且每步最多可以移动 $d_i$ 块地砖。 不幸的是，靴子的打包方式使得 Farmer John 在任何时候只能访问最上面的一双靴子。因此，Farmer John 可以随时穿上最上面的一双靴子（丢弃旧靴子）或丢弃最上面的一双靴子（使下一双靴子可访问）。 Farmer John 只能在地砖上更换靴子。如果该地砖上有 $f$ 英尺的雪，那么他脱下的靴子和穿上的靴子都必须能够承受至少 $f$ 英尺的雪。他丢弃但未穿过的中间靴子不需要满足此限制。 请帮助 Farmer John 最小化浪费，确定他到达谷仓需要丢弃的最少靴子对数。假设 Farmer John 最初没有穿任何靴子。

第一行包含两个以空格分隔的整数 $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$ 双靴子可以承受的最大雪深。第二个整数是 $d_i$，表示第 $i$ 双靴子的最大步长。保证 $0 \leq s_i \leq 10^9$ 且 $1 \leq d_i \leq N-1$。 靴子按从上到下的顺序描述，因此第 $1$ 双靴子是背包中最上面的一双，依此类推。

输出应包含一个整数，表示 Farmer John 需要丢弃的最少靴子对数。保证 Farmer John 能够到达谷仓。

题目来源：Brian Dean 和 Dhruv Rohatgi