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