泥泞道路
时间限制:1秒 内存限制:256M
【题目描述】
牧场里下了一场暴雨,泥泞道路上出现了许多水坑,约翰想用一批长度为 \(L\) 的木板将这些水坑盖住.
牧场里的道路可以看成一根数轴,每个水坑可以用数轴上的两个坐标表示,如 \((3,6)\) 表示从 \(3\) 到 \(6\) 有一个长度为 \(3\) 的水坑。所有的水坑都是不重叠的,\((3,6)\) 和 \((6,9)\) 可以出现在同一个输入数据中,因为它们是两个连续的水坑,但不重叠。
请你帮助约翰计算最少要用多少块木板才能将所有水坑盖住。
【输入格式】
第 1 行有二个用空格隔开的整数 \(N\) 和 \(L\)。其 \(N\),表示水坑总数,\(L\) 为木板长度。
接下来的 \(N\) 行每行两个整数 \(s_i\) 和 \(e_i\) ,表示一个水坑的左端点坐标和右端点坐标。
【输出格式】
一个整数,表示约翰盖住所有水坑最少要用多少块长为 \(L\) 的木板.
【输入输出样例】
Input
3 3
1 6
13 17
8 12
Output
5
【数据限制】
对于 \(100\%\) 的数据,\(1≤N≤10000\),\(0≤s_i<e_i≤10^9\)。
【来源】
Mr.he