Description

John wants to know when the previous shipment of feed arrived. Before that shipment arrived, his cows had just finished all the feed that was originally in the barn. He received $F1(1\le F1\le 10^6)$ kilograms of feed. Unfortunately, he no longer remembers which day that was. By day $D(1\le D\le 2\times 10^3)$, there are still $F2(1\le F2\le F1)$ kilograms of feed left in the barn.

John has $C(1\le C\le 100)$ cows, and each cow eats exactly $1$ kilogram of feed per day. Due to various reasons, each cow starts eating at the barn on some day and leaves on some day, so the feed consumption may vary greatly between different days. Each cow eats on both the day it arrives and the day it leaves. Given today’s day $D$, write a program to determine when the feed was most recently delivered. Today the cows have already eaten, and on the delivery day the cows had not yet eaten.

If there are multiple possible answers, output the largest one (i.e., the most recent).

Input Format

Line $1$: Four integers $C$, $F1$, $F2$, $D$, separated by spaces.

Lines $2$ to $C+1$: Each line contains two integers separated by spaces, representing the day a cow starts eating at the barn and the day it leaves.

Output Format

A single positive integer: the day when the previous shipment of feed arrived.

3 14 4 10
1 9
5 8
8 12

6

Hint

Sample Explanation

The previous shipment delivered $14$ kilograms of feed, and there are now $4$ kilograms left. In the last $10$ days, $3$ cows have come to eat.

John received $14$ kilograms of feed on day $6$. They ate $2$ kilograms on day $6$, $2$ kilograms on day $7$, $3$ kilograms on day $8$, $2$ kilograms on day $9$, and $1$ kilogram on day $10$, leaving exactly $4$ kilograms.

Constraints

$1\le F2\le F1\le 10^6$, $1\le D\le 2\times 10^3$, $1\le C\le 100$.

Translated by ChatGPT 5