#P2339. [USACO04OPEN] Turning in Homework G

[USACO04OPEN] Turning in Homework G

题目描述

贝茜有 C C ( 1C1000 1 \leq C \leq 1000 )门科目的作业要上交,之后她要去坐巴士和奶牛同学回家。

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

输入格式

第一行:三个整数 CCHHBB1C1000,1H1000,0BH1 \le C \le 1000,1 \le H \le 1000,0 \le B \le H

第二行到 C+1C+1 行:第 i+1i+1 行有两个整数 XiX_iTiT_i0XiH,0Ti100000 \le X_i \le H,0 \le T_i \le 10000

BB 表示车站位置。

XiX_i 表示第 ii 份作业应该在 XiX_i 这个位置交。

TiT_i 表示这个位置(教室)的这个科目老师(也就是收这份作业的老师)下课的时间。

输出格式

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

4 10 3
8 9
4 21
3 16
8 12
22

提示

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