大样例下载

题目描述

最近非常流行“旅游打卡”。

旅游打卡，是一个网络用语，意思是指“我看到、我来过、我拍过、我走了”。

小明就非常热衷“旅游打卡”。

这天，小明来到著名的“长街”旅游景区。

“长街”呈一条直线，长度为 L。我们可以把它看成一个数轴，长街的一头是原点，坐标为 0，另一头是终点，坐标为 L。“长街”出口位于坐标 C 处。

初始时（记为 0 时刻），小明在数轴原点 0 处。

小明希望完成 N 次打卡拍照。

第 i 次打卡处的坐标为 $X_i$，该次打卡开放时刻为 $T_i$（即该时刻及之后时刻才允许游客打卡拍照）。可能有多次打卡处坐标重合，但打卡开放时间不同。

小明在长街上每走 1 个单位距离，需要花费 1 个单位时间。打卡拍照时间忽略不计。

所有打卡结束后，小明会赶到出口处。

由于还要赶去下一个景区“打卡”，小明想知道，自己赶到出口处的最早时刻是多少？

你能帮助他吗？

输入格式

第一行：三个整数 $N, L, C$；

接下来 $N$ 行：每行两个整数 $X_i, T_i$，分别表示一个打卡处的坐标及允许打卡的开始时刻。

输出格式

一个整数，表示小明赶到出口处的最早时刻。

样例输入

4 10 3
8 10
4 21
3 16
8 12

样例输出

22

样例解释

小明希望完成 4 次打卡，不妨按输入顺序编号为：

(1) 8 10

(2) 4 21

(3) 3 16

(4) 8 12

小明可以这样来完成打卡：

首先，小明在时刻 0 从坐标 0 出发走到第一个打卡坐标 8 处，用时 8 个单位时间，等 2 个单位时间，完成打卡(1)，再等 2 个单位时间，完成打卡(4)，然后走到坐标 4 处，用时 4 个单位时间，等 5 个单位时间，完成打卡(2)，最后走到坐标 3 处，用时 1 个单位时间，完成打卡(3)。此处恰好是出口，此时为时刻 22。

数据范围

$1 ≤ N, L ≤ 1000, 0 ≤ C, X_i ≤ L, 0 ≤ T_i ≤ 10000$