Description
冬天到了，农场上又下起了雪。从农舍到牛棚一共有N块瓷砖，编号为1到N，第i块瓷砖上积雪的深度为fi英尺。
Farmer John必须从第一块瓷砖走到第N块瓷砖去叫醒奶牛们。第一块瓷砖在农舍的屋檐下，第N块瓷砖在牛棚的屋檐下，所以这两块砖上没有积雪。但是走在其他的瓷砖上时，Farmer John需要穿靴子了。
Farmer John一共有B双靴子，编号为1到B。一些靴子比较结实，一些靴子比较轻便，具体地说，第i双靴子能够让FJ在最多si英尺的积雪中每步最多前进di。
不幸的是，这些靴子都套在一起，使得Famer John在任何时刻只能拿到最上面的那一双。所以在任何时刻，Farmer John可以穿上最上面的那一双或者是丢弃最上面的那一双（使的她可以拿到下面那一双）。
Farmer John只有站在瓷砖上的时候才能换靴子，如果这块瓷砖上的积雪有f英尺，那么他换下来的和换上的靴子都要能够承受至少f英尺的积雪。中间没有穿，直接丢掉的靴子无需满足这一限制。
帮助Farmer John确定他最少需要丢弃多少双靴子。你可以假设一开始时候，他没有穿靴子。
Input
第一行，两个整数N和B，代表有N块瓷砖，B双靴子（2≤N,B≤250）
第二行，用空格隔开的N个整数，第i个整数fi，表示第i块瓷砖上，积雪的深度（0≤fi≤10^9）.f1=fN=0
接下来B行，每行两个用空格隔开的整数si和di，描述第i双靴子能够承受的最大的积雪深度si和这双靴子能够最多向前步数di。（0≤si≤10^9,1≤di≤N-1）
Output
一行，一个整数，表示Farmer John成功大道牛棚的前提下，需要丢弃的最小的靴子的双数.
10 4
0 2 8 3 6 7 5 1 4 0
2 3
4 2
3 4
7 1