题目描述

到冬天了，这意味着下雪了！从宿舍到教学楼的路上有$\red{N}$块地砖，方便起见编号为$\red{1...N，}$第$\red{i}$块地 砖上积了$\red{f_i}$英尺的雪。

公交车从$\red{1}$号地砖出发，他必须到达$\red{N}$号地砖才能到达教学楼上课。$\red{1}$号地砖在宿舍的屋檐下，$\red{N}$号地 砖在教学楼的屋檐下，所以这两块地砖都没有积雪。但是在其他的地砖上，公交车只能穿靴子了！

在公交车的恶劣天气应急背包中，总共有$\red{B}$双靴子，编号为$\red{1...B}$。其中某些比另一些结实，某些比 另一些轻便。具体地说，第i双靴子能够让公交车在至多$\red{s_i}$英尺深的积雪中行走，能够让公交车每步至 多跨$\red{d_i}$。

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

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

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

输入格式

第一行包含两个空格分隔的整数$\red{N}$和$\red{B(2<=N,B<=250)}$。

第二行包含$\red{N}$个空格分隔的整数。第$\red{i}$个整数为$\red{f_i，}$即$\red{i}$号地砖的积雪深度$\red{(0<=f_i<=10^9)}$。输入保 证$\red{f_1=f_N=0}$。

下面$\red{B}$行，每行包含两个空格分隔的整数。第$\red{i+2}$行的第一个数为$\red{s_i，}$表示第 双靴子能够承受的最 大积雪深度。第$\red{i+2}$行的第二个数为$\red{d_i，}$表示第$\red{i}$双靴子的最大步长。输入保证$\red{0<=s_i<=10^9}$以及$\red{1<=d_i<=N-1}$ 。

输出格式

输出包含一个整数，为公交车需要丢弃的靴子的最小双数。输入保证公交车能够到达教学楼。

样例

输入样例

10 4
0 2 8 3 6 7 5 1 4 0
2 3
4 2
3 4
7 1

输出样例

2