Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: keksiukai.in

Rezultatų failas: keksiukai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Keksiukai

Julius neseniai išgirdo apie naujai atidarytą "valgyk kiek telpa" keksiukų kepyklėlę. Jau sekančią dieną jis pusryčiams nukeliavo į kepyklėlę ir ten pamatė N į vieną eilę išdėstytų keksiukų. Kiekvienas keksiukas turėjo etiketę, nurodančią, jog i-tasis keksiukas turi F_i saldumo bei S_i rūgštumo.

Perskaitęs kepyklėlės taisykles Julius sužinojo, jog leidžiama suvalgyti neribotą kiekį iš eilės einančių keksiukų. Tai yra, Julius gali pasirinkti tik vieną iš eilės einantį keksiukų intervalą. Taipogi griežtai draudžiama keisti keksiukų tvarką.

Julius dievina saldžius keksiukus, bet ne įtin mėgsta rūgštumą. Julius savo pusryčių saldumą skaičiuoja kaip visų jo suvalgytų keksiukų saldumo sumą, o rūgštumą, kaip rūgščiausio jo suvalgyto keksiuko rūgštumą.

Julius prašo jūsų išsiaiškinti, koks yra minimalus jo pusryčių rūgštumas, jeigu jis nori, kad viso valgio saldumas būtų bent M.

Pradiniai duomenys

Pirmoje eilutėje yra skaičiai N ir M (1\\leqN\\leq10^5,1\\leqM\\leq10^{18}) - keksiukų skaičius bei minimalus valgio saldumas.

Sekančiose N eilučių yra po du skaičius F_i bei S_i (1\\leqF_i\\leq10^9,1\\leqS_i\\leq10^9) - i-tojo keksiuko saldumas bei rūgštumas.

Rezultatai

Išveskite vieną skaičių - minimalų Juliaus pusryčių rūgštumą.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5 10
4 10
6 15
3 5
4 9
3 6
 
9