徐老师的比赛安排
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
$CSP$ 的复赛马上就要到啦！为了让同学们能够模拟真实的比赛环境，徐老师特意买了几台云桌面服务器，安装了 $NOI-Linux$，这样就可以让同学们尝试最真实的比赛环境当然，一台云桌面服务器并不能允许两位同学同时使用，所以徐老师头疼的地方来了，他希望同学们在进入比赛环境后，并不只是摸摸看看，而是能打一场模拟赛，做一套题，这样才能最真实的体验比赛环境
也就是说，如果来的同学比服务器数量多，那么后来的同学就只能等着，等到前面的同学打完比赛，再接上
现在徐老师已经统计了明天每位同学的报名信息，第 $i$ 位报名的同学将会在 $t_i$ 时刻（单位为分钟）上线排队，并且他最多愿意等待 $w_i$ 分钟，如果超过时间了他就会离开（毕竟现在的同学学习都很忙，没有功夫一直排队）
而每一位同学在登录云桌面以后都需要花费 $m$ 分钟来打一场模拟赛，打完就会离开
现在徐老师打算按排队顺序（即先排队的先体验）让每位同学参与体验，他想知道最少需要购买几台云桌面服务器，才能让所有同学都能够体验到真实的比赛环境？
输入格式
输入第一行包含两个整数 $n,m$，分别表示同学人数和一场模拟赛比赛的时间接下来 $n$ 行，每行包含两个整数 $t_i,w_i$ 分别表示第 $i$ 位同学到达的时刻 $t_i$ 和他最多愿意等待的时间 $w_i$
提示：输入顺序就是排队顺序，即保证 $t_i$ 不递减
|测试点|$n$|特殊性质|
|:---:|:---:|:---:|
|$1$|$n \leq 5$|无|
|$2 \sim 4$|$n \leq 1000$|无|
|$5 \sim 6$|$n \leq 10^5$|所有 $w_i = m$|
|$7 \sim 10$|$n \leq 10^5$|无|
对于所有数据满足：$1 \leq t_i,w_i,m \leq 10^9$
|:---:|:---:|:---:|
|$1$|$n \leq 5$|无|
|$2 \sim 4$|$n \leq 1000$|无|
|$5 \sim 6$|$n \leq 10^5$|所有 $w_i = m$|
|$7 \sim 10$|$n \leq 10^5$|无|
对于所有数据满足：$1 \leq t_i,w_i,m \leq 10^9$
输出格式
输出一个整数表示徐老师最少需要购买几台云桌面服务器样例
5 3
1 1
2 30
3 10
3 1
5 33提示
第 $1$ 分钟：$1$ 号到达，开始体验，并在 $1+3=4$ 时刻结束第 $2$ 分钟：$2$ 号到达，开始体验，并在 $2+3=5$ 时刻结束
第 $3$ 分钟：$3$ 号到达，开始体验，并在 $3+3=6$ 时刻结束
第 $3$ 分钟：$4$ 号到达，此时没有机器能够使用，所以他需要等，他最多等到 $3+1=4$ 分钟
第 $4$ 分钟：$1$ 号体验结束，轮到 $4$ 号开始体验，并在 $4+3=7$ 时刻结束
第 $5$ 分钟：$5$ 号到达，此时 $2$ 号体验结束，正好 $5$ 号接上体验
可以发现至少需要 $3$ 台云桌面服务器
【CSP-J国庆公开赛】第三场
- 状态
- 已结束
- 规则
- IOI
- 题目
- 4
- 开始于
- 2023-10-2 13:00
- 结束于
- 2023-10-10 21:00
- 持续时间
- 200 小时
- 主持人
-
TeacherX
- 参赛人数
- 61