题目描述

徐老师最近在玩一个很有趣的游戏《太空穿梭》

这个游戏中共有 $n$ 个地点，玩家需要从 $1$ 号节点经过不断的空间跳跃到达 $n$ 号节点

在玩家进行空间跳跃的过程中，每个地点都会有外星人来进攻玩家，第 $i$ 个地点的外星人攻击力为 $a_i$

在这个游戏中，玩家需要乘坐宇宙飞船才能够进行空间跳跃，而每个玩家在一开始都拥有 $m$ 艘宇宙飞船，利用微缩技术存放在游戏背包中，每一艘宇宙飞船都有自己的防御能力 $b_i$ 以及空间跳跃能力 $c_i$ 。而一艘宇宙飞船在拿出背包后就会变大，无法重新放进背包。

只要某个地点的外星人攻击力不超过当前乘坐的宇宙飞船的防御能力，则不会被外星人攻破，玩家就可以在这个地区安然无恙，而外星人会无差别的攻击这个地点出现的所有飞船，也就是如果玩家在某个地区拿出一个防御能力小于当地外星人攻击能力的飞船，飞船会立刻被摧毁。

也就是意味着如果玩家需要在某个地点从 $A$ 号宇宙飞船换乘到 $B$ 号宇宙飞船，那么要保证 $A$ 和 $B$ 两艘飞船都不会被当地的外星人攻破。

而宇宙飞船的空间跳跃能力 $c_i$ 则表示在乘坐这一艘飞船时，玩家最多能够一次跨越 $c_i$ 个编号的地点，例如当前所处 $x$ 号地点，那么乘坐这艘飞船可以任意穿梭于编号区间 $[x - c_i, x + c_i]$ 的地点，当然，空间穿梭不能跳跃到小于 $1$ 和大于 $n$ 的地点

但是徐老师这一次携带的宇宙飞船数量太多了，导致他每次只能拿出最靠外面（编号最小）的那一艘飞船。

现在徐老师想知道他最少需要拿出几艘飞船，才能安全到达 $n$ 号节点？

输入格式

输入第一行包含两个整数 $n,m$ ，表示地点的数量以及徐老师背包里宇宙飞船的数量

输入第二行包含 $n$ 个数字 $a_i$ ，分别表示每个地点的外星人攻击力

接下来 $m$ 行，每行包含两个整数 $b_i,c_i$ 分别表示第 $i$ 艘宇宙飞船的防御股能力和空间跳跃能力

`输出一行表示徐老师最少需要拿出几艘飞船。

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

对于 $20\%$ 的数据满足： $2 \leq n,m \leq 10$

对于 $100\%$ 的数据满足：$2 \leq n,m \leq 250, 0 \leq a_i,b_i \leq 10^9, 1 \leq c_i \leq n - 1$

特别的保证： $a_1 = a_n = 0$

在下列比赛中: