到冬天了，这意味着下雪了！从农舍到牛棚的路上有N块地砖，方便起见编号为1…N，第i块地砖上积了fi英尺的雪。Farmer John从1号地砖出发，他必须到达N号地砖才能叫醒奶牛们。1号地砖在农舍的屋檐下，N号地砖在牛棚的屋檐下，所以这两块地砖都没有积雪。但是在其他的地砖上，Farmer John只能穿靴子了！

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

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

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

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

输入格式（文件名：snowboots.in）：

第一行包含两个空格分隔的整数N和B（2≤N,B≤250）。第二行包含N个空格分隔的整数。第i个整数为f$_i$，即i号地砖的积雪深度（0≤f$_i$≤10$^9$）。输入保证f$_1$=f$_N$=0。

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