测试数据来自 system/2194

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　一场大雨，小H家门前的河水猛涨！淹没了河中的石墩，具体来说，河上有 \(N\) 块石墩，方便起见编号为 \(1..N\)，第 \(i\) 块石墩淹没于水下 \(f_i\) 厘米。

　　小H需要从岸边的 1 号石墩出发，通过河中的石墩，到达河对岸的 \(N\) 号石墩，然后前往自己的学校。1 号与 \(N\) 号石墩在河岸上，所以这两块石墩没有被淹没。但是在其他的石墩上，小H只能穿涉水靴了！

　　在小H的大书包中总共有 \(M\) 双涉水靴，编号为 \(1..M\)。其中第 \(i\) 双靴子能够让小H在至多 \(s_i\) 厘米深的水中行走，能够让小H每步至多前进 \(d_i\) 块石墩。

　　因为这些靴子按编号顺序从上到下装在书包中，所以小H在任何时刻只能拿到最上面的那一双。在任何时刻，小H可以丢弃原来穿着的靴子，换上书包最上面的一双，或是直接丢弃最上面的那一双，使得可以拿到紧接着的下面一双。

　　小H只有在石墩上的时候才能换靴子。如果这块石墩淹没在水下 \(f\) 厘米，他换下来的靴子和他换上的那双靴子都要能够承受至少 \(f\) 厘米的水深。中间没有穿就丢弃的靴子无需满足这一限制。

　　请你帮助小H确定他最少需要丢弃多少双的靴子。你可以假设小H最开始穿着第一双涉靴站在第1个石墩上的。

【输入格式】

　　第一行包含两个空格分隔的整数 \(N\) 和 \(M\)。
　　第二行包含 \(N\) 个空格分隔的整数。第 \(i\) 个整数为 \(f_i（0≤f_i≤10^9）\) ，即 \(i\) 号石墩的积水深度。输入保证 \(f_1=f_N=0\)。
　　下面 \(M\) 行，每行包含两个空格分隔的整数。第 \(i+2\) 行的第一个数为 \(s_i\)，表示第 \(i\) 双靴子能够承受的最大积水深度。第 \(i+2\) 行的第二个数为 \(d_i\)，表示第 \(i\) 双靴子的最大步长。输入保证 \(0≤s_i≤10^9\) 以及 \(1≤d_i≤N−1\)。

【输出格式】

　　输出包含一个整数，为小H需要丢弃的靴子的最小数目（单位：双）。

【输入输出样例】

　Input

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

　Output

2

【样例解释】

　　小H穿着第1双涉水靴从1号石墩跳到2号石墩；
　　然后在2号石墩丢弃穿着的第一双靴子，换上第二双靴子后，跳到4号石墩；
　　然后在3号石墩丢弃穿着的第二双靴子，换上第三双靴子或，到8号石墩，接着跳道10号石墩；
　　然后小H穿着第3双靴子到学校去了。
　　所以在整个过程中，小H丢弃了前两双靴子。

【数据限制】

　　对于 \(100\%\) 的数据，\(2≤N,M≤250\)。

【来源】

　　Mr.he