Задачі
Великий масив Діно
Великий масив Діно
Одного разу коли Діно розв'язував задачу, пов'язану із масивами, він помітив що розмір усіх масивів рівний що найбільше `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