 favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

# 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 `106`. 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: (`a1`, `b1`), (`a2`, `b2)`, ..., (`an`, `bn`). Then for each of these pairs he inserts into array the number `bi ai` 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 (1n`105`). Each of the next n lines contains pair (`ai`, `bi`) (1`ai`, `bi``105`). 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.

Time limit 1 second
Memory limit 128 MiB
Input example #1
```3
1 2
3 6
2 1
3```
Output example #1
`2`
Source 2019-2020 Republic Azerbaijan, Semifinals