e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

Azərbaycan Respublika Olimpiadasının yarımfinalı 2019-2020

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

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

Дино сначала создает пустой массив и выбирает n пар чисел: (a1, b1), (a2, b2), ..., (an, bn). Затем для каждой из этих пар он вводит в массив число bi в количестве ai. Например, если первая пара будет (3, 5), то в массив число 5 будет введено 3 раза. После этого Дино решает расположить данный массив в неубывающем порядке, но так как массив очень большой, компьютер Дино не может выполнить данное расположение. Ему интересно в данном упорядоченном массиве k-ое (массив нумеруется с числа 1) число. Помогите Дино найти данное число.

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

В первой строке задано целое число n (1n105). В каждой из следующих n строк содержится пара (ai, bi) (1ai, bi105). Последняя строка содержит число k. Гарантировано, что существует k-ое число в массиве.

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
3
1 2
3 6
2 1
3
Выходные данные #1
2
Источник Полуфинал Республиканской олимпиады Азербайджана 2019-2020