#2042. 公交车与靴子
公交车与靴子
题目描述
到冬天了,这意味着下雪了!从宿舍到教学楼的路上有块地砖,方便起见编号为第块地 砖上积了英尺的雪。
公交车从号地砖出发,他必须到达号地砖才能到达教学楼上课。号地砖在宿舍的屋檐下,号地 砖在教学楼的屋檐下,所以这两块地砖都没有积雪。但是在其他的地砖上,公交车只能穿靴子了!
在公交车的恶劣天气应急背包中,总共有双靴子,编号为。其中某些比另一些结实,某些比 另一些轻便。具体地说,第i双靴子能够让公交车在至多英尺深的积雪中行走,能够让公交车每步至 多跨。
不幸的是,这些靴子都套在一起,使得公交车在任何时刻只能拿到最上面的那一双。所以在任何时 刻,公交车可以穿上最上面的一双靴子(抛弃原来穿着的那双),或是丢弃最上面的那一双靴子(使 得可以拿到下面那一双)。
公交车只有在地砖上的时候才能换靴子。如果这块地砖的积雪有英尺,他换下来的靴子和他换上的那 双靴子都要能够承受至少英尺的积雪。中间没有穿就丢弃的靴子无需满足这一限制。
帮助公交车最小化他的消耗,确定他最少需要丢弃的靴子的双数。你可以假设公交车在开始的时候没 有穿靴子。
输入格式
第一行包含两个空格分隔的整数和。
第二行包含个空格分隔的整数。第个整数为即号地砖的积雪深度。输入保 证。
下面行,每行包含两个空格分隔的整数。第行的第一个数为表示第 双靴子能够承受的最 大积雪深度。第行的第二个数为表示第双靴子的最大步长。输入保证以及 。
输出格式
输出包含一个整数,为公交车需要丢弃的靴子的最小双数。输入保证公交车能够到达教学楼。
样例
输入样例
10 4
0 2 8 3 6 7 5 1 4 0
2 3
4 2
3 4
7 1
输出样例
2
统计
相关
在下列比赛中: