【题目描述】

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

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

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

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

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

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

【输入格式】（snowboots.in）：

第一行包含两个空格分隔的整数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。

【输出格式】（snowboots.out）：

输出包含一个整数，为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