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. \InputFile 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. \OutputFile Print the $k$-th number in non-decreasing array.