Большой массив Дино

Однажды когда Дино решал задачу, связанную с массивами, он увидел что размер всех массивов равен самое большее $10^6$. Так как Дино является динозавром, ему это число показалось очень маленьким. Поэтому он решил создать большой массив.

Дино сначала создает пустой массив и выбирает $n$ пар чисел: $(a_1,b_1),(a_2,b_2),...,(a_n,b_n)$. Затем для каждой из этих пар он вводит в массив число $b_i$ в количестве $a_i$. Например, если первая пара будет $(3,5)$, то в массив число $5$ будет введено $3$ раза. После этого Дино решает расположить данный массив в неубывающем порядке, но так как массив очень большой, компьютер Дино не может выполнить данное расположение. Ему интересно в данном упорядоченном массиве $k$-ое (массив нумеруется с числа $1$) число. Помогите Дино найти данное число.

Входные данные

В первой строке задано целое число $n(1\le n\le 10^5)$. В каждой из следующих $n$ строк содержится пара $(a_i,b_i)(1\le a_i,b_i\le 10^5)$. Последняя строка содержит число $k$. Гарантировано, что существует $k$-ое число в массиве.

Выходные данные

Выведите $k$-ое число в неубывающем массиве.

Примеры