# Полуфинал Республиканской олимпиады Азербайджана 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`

. Since Dino is a dinosaur, this number seemed very small to him. Therefore, he decided to create a big array.^{6}

Dino first creates an empty array and selects **n** pairs of numbers: (`a`

, _{1}`b`

), (_{1}`a`

, _{2}`b`

, ..., (_{2})`a`

, _{n}`b`

). Then for each of these pairs he inserts into array the number _{n}`b`

times. For example,if the first pair is (_{i} a_{i}**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** ≤ **n** ≤ `10`

). Each of the next ^{5}**n** lines contains pair (`a`

, _{i}`b`

) (_{i}**1** ≤ `a`

, _{i}`b`

≤ _{i}`10`

). The last line contains number ^{5}**k**. It is guaranteed that **k**-th number exists in array.

#### Output

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

3 1 2 3 6 2 1 3

2