#P1022. 乌拉乎与餐厅
乌拉乎与餐厅
题目描述
乌拉乎发现,共有 名顾客相继抵达某一家餐厅。对于第 名顾客来说,他会在 时刻到达,最多可以在店外排队等待 分钟,如果超时,则这名顾客会离开,不吃饭。每位顾客的用餐时间都相同,均为 分钟。顾客吃饭采取先到先得原则,即哪位顾客先到,哪位顾客先排队,先用餐。请问餐厅至少需要安排多少桌子(一个桌子招待一名顾客)才能让所有顾客都吃上饭。
输入格式
第一行输入两个正整数 ,表示顾客数量,顾客用餐时间。
接下来有 行,每行两个正整数 分别表示每一位顾客的到达时间,最多排队时间。保证读入顺序就是顾客吃饭排队顺序,即 不递减。
特别的,当相同时,顾客会以输入顺序排队和用餐。
输出格式
输出一行一个整数表示店家至少要安排多少张桌子。
4 5
1 10
5 1
6 2
7 2
3
5 3
1 1
2 30
3 10
3 1
5 3
3
数据点说明
对于所有的测试点,。
测试点编号 | 特殊性质 | |
---|---|---|
1 | 5 | |
2-4 | 1000 | |
5-6 | 100000 | 对于所有的 ,有 |
7-10 |