Responsive image

问题 H: 泥泞路

问题 H: 泥泞路

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 47
[提交][状态][讨论版][命题人:]

题目描述

暴雨过后，TY的农场到镇上的公路上有一些泥泞路，他有若干块长度为 L 的木板可以铺在这些泥泞路上，问他至少需要多少块木板，才能把所有的泥泞路覆盖住。

输入描述


第一行为正整数  n  和  L ，分别表示有n段泥泞路和长度为L的木板；

接下来  n  行，每一行两个整数  s  和  e ，表示每一段泥泞路的起点和终点。

输出描述

仅一个正整数，表示木板数。

样例输入

3 3
1 6
13 17
8 12

样例输出

5

提示



对于100%的数据，n,L≤10000，s≤e≤109

如果泥泞路两端是1和3，则说明是一个1到2，2到3的长度为2的泥泞路，故而一个长度为2的木板可以覆盖1到3。

分析样例：

所以样例一共需要5块木板



第1块木板：1到4



第2块木板：4到7



第3块木板：8到11



第4块木板：11到14



第5块木板：14到17



 



 




























[提交][状态]
ACM算法攻关部