[USACO04OPEN] Turning in Homework G

题目描述

贝茜有 $ C $ ( $ 1 \leq C \leq 1000 $ )门科目的作业要上交,之后她要去坐巴士和奶牛同学回家。 每门科目的老师所在的教室排列在一条长为 $ H $ ( $ 1 \leq H \leq 1000 $ )的走廊上,他们只在课后接收作业,交作业不需要时间。贝茜现在在位置0,她会告诉你每个教室所在的位置,以及走廊出口的位置。她每走1个单位的路程,就要用1秒。她希望你计算最快多久以后她能交完作业并到达出口。

输入输出格式

输入格式


第一行:三个整数 $C$,$H$ 和 $B$,$1 \le C \le 1000,1 \le H \le 1000,0 \le B \le H$。 第二行到 $C+1$ 行:第 $i+1$ 行有两个整数 $X_i$ 和 $T_i$,$0 \le X_i \le H,0 \le T_i \le 10000$。 $B$ 表示车站位置。 $X_i$ 表示第 $i$ 份作业应该在 $X_i$ 这个位置交。 $T_i$ 表示这个位置(教室)的这个科目老师(也就是收这份作业的老师)下课的时间。

输出格式


单个整数,表示贝西交完作业后走到车站的最短时间

输入输出样例

输入样例 #1

4 10 3
8 9
4 21
3 16
8 12

输出样例 #1

22

说明

走到坐标 8 处,第 9 分钟交一本作业,等到第 12 分钟时,交另一本作业。再走到坐标 4 处交作业,最后走到坐标 3 处,交最后一本作业,此地就是车站所在位置,共用时 22 分钟