# Полуфинал Республиканской олимпиады Азербайджана 2018-2019

# 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 data

First line contains number n (1 ≤ n ≤ `10^5`

). Each of the next n lines contains pair (`a[i]`

, `b[i]`

) (1 ≤ `a[i]`

, `b[i]`

≤ `10^5`

). The last line contains number k. It is guaranteed that k-th number exists in array.

## Output data

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

## Examples

3 1 2 3 6 2 1 3

2