A2592 | 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能够到达牛棚。