【题目描述】

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

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

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

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

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

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

【输入格式】

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

第二行包含 N 个空格分隔的整数。第 i 个整数为 fi，即 i 号地砖的积雪深度（0≤fi≤10^9）。输入保证f1=fn=0。

下面 B 行，每行包含两个空格分隔的整数。第 i+2 行的第一个数为 si，表示第 i 双靴子能够承受的最大积雪深度。第 i+2 行的第二个数为 di，表示第 i 双靴子的最大步长。输入保证 0≤si≤10^9 以及 1≤di≤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