Məsələlər
Dinonun böyük massivi
Dinonun böyük massivi
Bir gün Dino massivlərlə bağlı məsələ işləyəndə, bütün massivlərin ölçüsünün ən çoxu $10^6$ olduğunu gördü. Dino özü dinozavr olduğu üçün, bu ədəd ona çox kiçik gəldi. Buna görə də, o, böyük massiv yaratmaq qərarına gəldi.
Dino ilk olaraq, boş bir massiv yaradır və $n$ ədəd cütlüyü seçir --- $(a_1, b_1), (a_2, b_2), ..., (a_n, b_n)$. O, daha sonra isə, bu cütlüklərin hər biri üçün massivə $a_i$ qədər $b_i$ ədədini daxil edir. Məsələn, birinci cütlük $(3, 5)$ olsa, massivə $3$ dəfə $5$ daxil olunacaq. Sonda isə, Dino qərara gəlir ki, bu massivi azalmayan sırada düzsün, amma massiv böyük olduğu üçün Dinonun kompüteri sıralama əməliyyatını yerinə yetirə bilmir. Ona isə, sıralanmış massivdə $k$-cı (massiv $1$-dən nömrələnir) ədəd maraqlıdır. Bu ədədi tapmaqda Dinoya kömək edin.
\InputFile
İlk sətirdə $n~(1 \le n \le 10^5)$ tam ədədi verilir. Növbəti $n$ sətrin $i$-cisində $(a_i, b_i)~(1 \le a_i, b_i \le 10^5)$ cütlüyü verilir. Sonuncu sətirdə isə $k$ ədədi verilir. Zəmanət verilir ki, massivdə $k$-cı ədəd mövcuddur.
\OutputFile
Çıxışa azalmayan sırada düzülmüş massivdəki $k$-cı ədədi verin.
Giriş verilənləri #1
3 1 2 3 6 2 1 3
Çıxış verilənləri #1
2