1664: 饲料

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:26 通过:19

题目描述

         小兔子国王是一个伟大的国王。

小兔子国王想知道上一船饲料是什么时候运到的。在饲料运到之前,他的正好把仓库里原来的饲料全吃光了。然后,他收到了运来的F1千克饲料。遗憾的是,他已经不记得这是哪一天的事情了。到第D天为止,仓库里还剩下F2千克饲料。

小兔子国王养了C汪星人,每头每天都吃掉恰好1千克饲料。由于不同的原因,汪星人们从某一天开始在仓库吃饲料,又在某一天离开仓库,所以不同的两天可能会有差距很大的饲料消耗量。每头在来的那天和离开的那天都在仓库吃饲料。

给出今天的日期D,写一个程序,判断饲料最近一次运到是在什么时候。今天们已经吃过饲料了,并且饲料运到的那天们还没有吃过饲料。

输入格式

1行:四个整数CF1F2D,用空格隔开。

2~C+1行:每行是用空格隔开的两个数字,第i+1行描述第i来仓库吃饲料的时间S_i和离开的时间T_i

输出格式

输出共一行一个正整数,即上一船饲料最晚运到的时间,数据保证有解。

输入样例 复制

3 14 4 10
1 9
5 8
8 12

输出样例 复制

6

数据范围与提示

【样例解释】

上一船运来了14千克饲料,现在饲料还剩下4千克。最近10天里,有3来吃过饲料。

小兔子国王在第6天收到14千克饲料,当天吃掉2千克,第7天吃掉2千克,第8天吃掉3千克,第9天吃掉2千克,第10天吃掉1千克,正好还剩4千克。

【数据规模】

对于30%的数据: 1≤C≤301≤D≤200

对于100%的数据:1≤C≤1001≤F2≤F1≤1,000,0001≤D≤2,0001≤S_i≤T_i≤2,000