fisc

Consider n persons standing in line at a clerk's desk, in order to submit the income statements of certain companies. Each person has one or more statements to file.
We know that filing a statement takes exactly one minute and the filing of the first statement begins at minute 1.
For each person we know the number of statements he/she has to file and the limit minute up until that person can stand in line (after that minute expires that person would have to leave in order to see to other problems).
We know that a person is going to leave only if his/hers available time has expired and they failed to reach the desk orhe/she has reached the desk but he/she does not have enough time to file all his/hers statements (in which case he/she leaves without filing any statement).
The fiscal representative that receives the statements needs a break of exactly p minutes which he/she may take at any time, under the condition that the persons whose statements can be received remain the same as if he/she would take no break. Obviously, the fiscal representative cannot take a break while serving a client (namely while a person that is at the desk is filing statements). In case this is not possible the fiscal representative will take the break after he/she has finished receiving all statements it can receive.

Task

Find the earliest time when the fiscal representative can take his/her break.

Input data

The first line of input file fisc.in contains positive integer n, representing the number of persons standing in line. The following n lines contain information about the n persons standing in line. More specifically, the (i+1)^th contains two positive integers separated by a space, D L, where D represents the number of statements person i has to file and L the time limit for person i. The last line contains positive integer p, representing the number of break minutes of the fiscal representative.

Output data

Output file fisc.out will contain a single line with a positive integer representing the (first possible) minute when the fiscal representative can take a break.

Constraints and clarifications

• 0 < n <= 1000
• All values in the problem are positive integers.
• 0 < D <= 100
• 0 < L <= 10000
• 0 < p < 100
  

Time limit: 0.1 seconds/test

prof. Rodica Pintea
Bucharest "Grigore Moisil" High-School
Contact:ro_dica@yahoo.com