#2042. 公交车与靴子

公交车与靴子

题目描述

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

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

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

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

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

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

输入格式

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

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

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

统计

相关

在下列比赛中:

入门班3