1819: [NewOJ Week 6] 推箱子

内存限制:256 MB 时间限制:2 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:959 通过:271

题目描述

在一个高度为H的箱子前方,有一个长和高为N的障碍物。
障碍物的每一列存在一个连续的缺口,第i列的缺口从第l各单位到第h个单位(从底部由0开始数)。
现在请你清理出一条高度为H的通道,使得箱子可以直接推出去。
请输出最少需要清理的障碍物面积。
如下图为样例中的障碍物,长和高度均为5,箱子高度为2。(不需要考虑箱子会掉入某些坑中)
    

最少需要移除两个单位的障碍物可以造出一条高度为2的通道。

输入格式

输入第一行为两个正整数N和H,表示障碍物的尺寸和箱子的高度,1≤H≤N≤1000000
接下来N行,每行包含两个整数li和hi,表示第i列缺口的范围,0≤li≤hi<N

输出格式

输出一个数字表示答案。

输入样例 复制

5 2
2 3
1 2
2 3
1 2
2 3

输出样例 复制

2