本题没有可用的提交语言。

题目描述

农民约翰试图弄清楚他最后一批饲料何时到达。从一个空的谷物箱开始,他订购并收到了$F1(1 <= F1 <= 1,000,000)$公斤饲料。遗憾的是,他不确定饲料何时到达。在F1公斤中,$F2(1<=F2<=F1)$千克饲料留在$D$日$(1<=D<=2,000)$。他必须确定他的货物可能到达的最近一天。

他的每头$C(1<=C<=100)$奶牛每天只吃1公斤饲料。由于各种原因,奶牛在某一天到达并在另一个日子离开,因此两天的饲料消耗可能非常不同。输入数据告诉每头牛在哪几天。每头牛在她到达的那天和她离开的那天都吃了农民约翰的垃圾箱的饲料。

鉴于今天是$D$日,确定自他上次发货以来必须通过的最短天数。奶牛今天已经吃过饭了,货物在奶牛吃之前就到了。

输入

• 第1行:四个空间分隔整数$:C、F1、F2和D$

*第2行:$C+1$:行$i+1$包含两个空间分隔的整数,描述牛的存在。第一个整数告诉奶牛在农场的第一天;第二个整数告诉奶牛存在的最后一天。每一天都在1...2000的范围内。

输出

货物可能到达的最后一天,一个整数将永远是正的。 输入数 1

3 14 4 10
1 9
5 8
8 12

输出数位 1

6

提示

INPUT详细信息:

货物是14公斤饲料,农民约翰还剩4公斤。在过去的10天里,他有三头奶牛吃了一段时间的饲料。

OUTPUT 详细信息:

如果农民约翰在第$6$天开始吃$14$公斤饲料,那么在第$6$天和第$7$天,每天将吃掉$2$公斤。第$8$天,三公斤被吃掉。第$9$天,两公斤会被吃掉。第$10$天,一公斤会被吃掉。因此,总吃量为$2 + 2 + 3 + 2 + 2 + 1 = 10$,留下$4$公斤。 来源

USACO 2005年2月银牌