← 返回题目列表

Codeforces · 608/A

A. 埼玉毁坏酒店

中文机器翻译题面 查看原题

埼玉又不小心毁掉了一家酒店。为了回报酒店公司,杰诺斯自愿在其其他酒店之一运营一部电梯。电梯很特别——它从顶层开始,只能向下移动,而且容量无限。楼层编号从 0 到 s,电梯最初在时间 0 的楼层 s 启动。

电梯只需要 1 秒就可以准确地向下移动 1 层楼,载客时间可以忽略不计。杰诺斯收到了一份详细说明乘客到达时间和楼层的列表。请计算杰诺斯将所有乘客带到 0 楼需要多长时间(以秒为单位)。

输入

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

接下来的 n 行每行包含两个空格分隔的整数 fi 和 ti (1 ≤ fi ≤ s, 1 ≤ ti ≤ 1000) - 乘客编号 i 的楼层和到达时间(以秒为单位)。

输出

打印一个整数 - 将所有乘客带到 0 楼所需的最短时间(以秒为单位)。

示例

输入 #1

3 7
2 1
3 8
5 2

输出 #1

11

输入 #2

5 10
2 77
3 33
8 21
9 12
10 64

输出 #2

79

注意

在第一个示例中,将所有乘客带到 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 秒。