Одного разу коли Діно розв'язував задачу, пов'язану із масивами, він помітив що розмір усіх масивів рівний що найбільше '10^6' . Так як Діно є динозавром, йому це число здалося замалим, а тому він вирішив створити великий масив.
Діно на початку створює порожній масив і вибирає n пар чисел — (a1,b1),(a2,b2),...,(an,bn). Потім для кожної із цих пар він вводить в масив число bi в кількості ai. Наприклад, якщо перша пара буде (3,5), то в масиві число 5 буде записано 3 рази. Після цього Діно вирішує розташувати отриманий масив в неспадному порядку, але так як масив дуже великий, комп Діно не може виконати дане впорядкування. Його зацікавило k-е число (масив нумерується з 1). Допоможіть Діно знайти дане число.
В першому рядку задано натуральне число n (1≤n≤105). В кожному із наступних n рядків записана пара (ai,bi) (1≤ai,bi≤105). Останній рядок містить число k. Гарантовано, що існує k-е число у масиві.
Виведіть k-е число в неспадному масиві.