eolymp
bolt
Try our new interface for solving problems
Məsələlər

Dinonun böyük massivi

Dinonun böyük massivi

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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ə

Giriş verilənləri #1
3
1 2
3 6
2 1
3
Çıxış verilənləri #1
2
Mənbə Azərbaycan Respublika Olimpiadasının yarımfinalı 2019-2020