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.

Giriş verilənləri

İ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.

Çıxış verilənləri

Çıxışa azalmayan sırada düzülmüş massivdəki $k$-cı ədədi verin.

Nümunələr