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.
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ə
3 1 2 3 6 2 1 3
2