/ Vijos / 题库 /

宋神牛交作业

宋神牛交作业

背景

在北京第八十中学举行的第26界noi当中,宋文杰神牛以700分的满分成绩获得了noi金牌第一名,领先第二名400分……

描述

进了国家集训队之后,宋神牛为了为江苏争取荣誉,准备冲击国家队。为了冲击国家队,宋神牛必须完成一坨国家集训队作业。

他有N项作业要完成,经过了一个星期的努力,宋神牛完成了所有的作业(好强啊!!!)。这个时候,他来到twb和hwd那里,要提交作业。由于hwd和twb要看NBA,所以,第i项作业有一个最早提交时间Ei和提交地点Si。刚开始,宋神牛站在0号点。宋神牛由于常年做题,体质下降,从i号点走到j号点需要用|i-j|秒的时间。他提交完所有作业之后,还要到k号点坐公交车回家。

这个时候,宋神牛的mm打电话给宋神牛说:“你快回来啊,我想死你了。”宋神牛非常无奈,他想知道,最早什么时候能乘上公交车。

格式

输入格式

输入数据的第一行是三个整数N,M,k。分别代表宋神牛要提交N项作业,所有提交作业地点的坐标的最大值和最后乘公交车回家的地点。

接下来是N行,每行两个整数S和E,分别代表该项作业的提交地点和最早提交时间。

输出格式

输出一行一个整数,代表宋神牛最早啥时候乘上公交车。

样例1

样例输入1

4 10 3
8 9
4 21
3 16
8 12

样例输出1

22

限制

宋神牛说:“我mm等得急死了,我只给你1s!!”

提示

1<=N<=1000
1<=M<=1000
0<=k<=M
所有坐标为非负数
答案小于2^31-1

对样例的解释:
时间 行为
0 宋神牛走到8号点
8 宋神牛等1秒钟
9 宋神牛交了第一项作业
9 宋神牛等3秒钟,想着在夏天获得的那枚金牌……
12 宋神牛在8号点交给hwd第二项作业
12 宋神牛走回去到4号点,用4秒钟
16 宋神牛等待了5秒钟,想着他和他的mm在noi开幕式上认识的那个美妙的时刻
21 宋神牛交了他的作业
21 宋神牛走到了3号点
22 宋神牛交给twb最后一项作业
22 由于公交车站也是在3号点,所以他在22时刻就可以乘车回家咯

因此,宋神牛最早可以在22时刻乘上公交车,没有更好的方案了……

信息

ID
1576
难度
7
分类
动态规划 点击显示
标签
(无)
递交数
256
已通过
50
通过率
20%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库