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 106 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 — (a1,b1),(a2,b2),...,(an,bn). O, daha sonra isə, bu cütlüklərin hər biri üçün massivə ai qədər bi ə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.
İlk sətirdə n (1≤n≤105) tam ədədi verilir. Növbəti n sətrin i-cisində (ai,bi) (1≤ai,bi≤105) 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ışa azalmayan sırada düzülmüş massivdəki k-cı ədədi verin.