农场的冬天到了，这意味着下雪了！从农舍到谷仓的路上有 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 能够到达谷仓。

USACO