Задачи
Большой массив Дино
Большой массив Дино
Однажды когда Дино решал задачу, связанную с массивами, он увидел что размер всех массивов равен самое большее $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$) число. Помогите Дино найти данное число.
\InputFile
В первой строке задано целое число $n~(1 \le n \le 10^5)$. В каждой из следующих $n$ строк содержится пара $(a_i, b_i)~(1 \le a_i, b_i \le 10^5)$. Последняя строка содержит число $k$. Гарантировано, что существует $k$-ое число в массиве.
\OutputFile
Выведите $k$-ое число в неубывающем массиве.
Входные данные #1
3 1 2 3 6 2 1 3
Выходные данные #1
2