[Usaco2005 Feb]Feed Accounting 饲料计算

约翰想知道上一批饲料是什么时候运到的。在饲料运到之前，仓库中原有的饲料恰好已经被牛吃完。随后，他收到了一批共 $F_1$ 千克的饲料，但已经不记得具体的送达日期。

到第 $D$ 天为止，仓库中还剩下 $F_2$ 千克饲料。约翰养了 $C$ 头牛，每头牛每天恰好吃掉 $1$ 千克饲料。每头牛会从某一天开始在仓库吃饲料，并在另一天离开，因此不同日期的饲料消耗量可能相差很大。牛在到达当天和离开当天都会吃饲料。

已知今天是第 $D$ 天，请确定这批饲料最晚可能在哪一天运到。今天的牛已经吃过饲料，并且在饲料运到的当天，饲料先于牛进食到达。

输入格式

第一行包含 $4$ 个用空格分隔的整数 $C$、$F_1$、$F_2$ 和 $D$。

接下来 $C$ 行，每行包含 $2$ 个用空格分隔的整数，分别表示一头牛开始在仓库吃饲料的日期和离开的日期。牛在这两个日期及其之间的每一天都会吃饲料。

输出格式

输出一个正整数，表示这批饲料最晚可能运到的日期。

样例输入

3 14 4 10
1 9
5 8
8 12

样例输出

6

数据范围

• $1\le C\le 100$；
• $1\le F_1\le 10^6$；
• $1\le F_2\le F_1$；
• $1\le D\le 2\times 10^3$；
• 每头牛到达和离开的日期均在 $1$ 至 $2\times 10^3$ 之间。

来源与许可

本题为 USACO 2005 February 试题「Feed Accounting 饲料计算」，题面与测试数据整理自 BZOJ。

样例 1

输入

3 14 4 10
1 9
5 8
8 12

输出

6