问题 4765 --马丁的电梯

4765: 马丁的电梯

时间限制: 1 Sec  内存限制: 256 MB
提交: 140  解决: 60
[提交][状态][命题人:]

题目描述

一天早晨,马丁变成了一部很特别的电梯,电梯从顶层开始,只能向下移动,并且容量无限。 楼层从 0 到 s 编号,电梯最初在 0 时刻从 s 层开始。

电梯向下移动 1 层楼恰好花费 1 秒,而接载乘客的时间可以忽略不计。马丁收到了一份清单,详细说明乘客到达的时间和地点。 请确定马丁将所有乘客带到 0 层需要多长时间。

输入

第一行输入包含两个整数 n 和 s (1 ≤ n ≤ 100, 1 ≤ s ≤ 1000),分别是乘客人数和顶层数。

接下来的 n 行每行包含两个空格分隔的整数 f[i] 和 t[i] (1 ≤ f[i] ≤ s, 1 ≤ t[i] ≤ 1000),表示编号为 i 的乘客出现的楼层和出现时间(以秒为单位)。

输出

打印一个整数,表示将所有乘客带到 0 层所需的最少时间(以秒为单位)。
样例输入
Copy
3 7
2 1
3 8
5 2
样例输出
Copy
11

提示

在第一个示例中,将所有乘客带到 0 层至少需要 11 秒,一种合理的执行顺序如下:
1. 移动到 5 楼,花费 2 秒。
2. 接载乘客 3.
3. 移动到 3 楼,花费 2 秒。
4. 等待乘客 2 到达,花费 4 秒。
5. 接载乘客 2。
6. 移动到2楼,花费1秒。
7. 接载乘客 1。
8. 移动到 0 楼,花费 2 秒。
这给出了总共 2+2+4+1+2=11 秒。

来源

[提交][状态]