Big array of Dino

Once, when Dino was solving a problem related to arrays, he saw that the size of all arrays is at most $10^6$. Since Dino is a dinosaur, this number seemed very small to him. Therefore, he decided to create a big array.

Dino first creates an empty array and selects $n$ pairs of numbers: $(a_1,b_1),(a_2,b_2),...,(a_n,b_n)$. Then for each of these pairs he inserts into array the number $b_i{a}_i$ times. For example,if the first pair is $(3,5)$, the number $5$ will be inserted into array $3$ times. After that, Dino decides to arrange this array in non-decreasing order, but since the array is very large, Dino's computer cannot perform this arrangement. He is interested in the $k$-th (the array is numbered starting from $1$) number. Help Dino to find this number.

Input

First line contains number $n(1\le n\le 10^5)$. Each of the next $n$ lines contains pair $(a_i,b_i)(1\le a_i,b_i\le 10^5)$. The last line contains number $k$. It is guaranteed that $k$-th number exists in array.

Output

Print the $k$-th number in non-decreasing array.

Examples