There are cells labeled from to arranged in sequence. Cell contains a base, and cell contains a monster with health . There are soldiers deployed near the cells. The attack range of soldier is from cell to (i.e., cells ).
Each turn, both the monster and the soldiers perform the following actions in order (first the monster, then the soldiers):
Monster: If the monster's health is or more and it is not in cell , it moves one cell closer to the base (i.e., it moves to the cell with a number smaller).
Soldiers: Any soldier whose attack range includes the cell where the monster is currently located attacks the monster and reduces its health by .
If the monster's health drops to or below before it reaches cell , the monster dies in that cell, the defense is successful, and the game ends. If the monster reaches cell without its health dropping to or below, the defense fails and the game ends.
Determine whether the defense will succeed, and if so, find the number of the cell where the monster will die.
输入格式
The input consists of a single test case of the following format.
The first line contains three integers, , , and , representing the number of soldiers, the number of cells, and the monster's health, respectively. is between and (both inclusive). is between and (both inclusive). is between and (both inclusive).
The next lines each contain two integers, and , which represent the attack range interval of the -th soldier. Both and are between and (both inclusive). It is guaranteed that is less than or equal to .
输出格式
Output a single integer, the number of the cell where the monster will die if the defense is successful; otherwise, output .
