25130번 - Drvene daščice 스페셜 저지다국어

Kako se snižavaju temperature, tako i raste potražnja drva za ogrjev. Ispred poslovnice drva formirao se red, a na vrhu reda je naravno naš Gospodin Malnar.

Drvosječa Darko u svojoj radionici ima $n$ debla drva. Gospodin Malnar ima specifičan zahtjev te želi točno $k$ metara drva, što stavlja drvosječu Darku u probleme, no srećom sa sobom ima svoju vjernu pilu.

Debla su poslagana paralelno sa zidom poslovnice te će Darko postaviti svoju pilu okomito na njih i jednom snažno zasjeći, prepilivši time sva debla na putu. Naravno, poslovnicu Gospodin Malnar vidi kao koordinatni sustav, gdje su debla dužine paralelne s $y$-osi te drvosječa siječe sve dužine na nekom pravcu paralelnom s $x$-osi. No ekscentričnim zahtjevima Gospodina Malnara tu nije kraj, on zahtjeva sva tek prepiljena debla te od tih prepiljenih isključivo kraći kraj. Ako su krajevi jednakih duljina, zadovoljit će se s bilo kojim, ali dakako ne s oba.

Drvosječa Darko je ipak završio samo drvodjelsku srednju školu, pa nije siguran kako točno ispuniti svim zahtjevima Gospodina, zato je vas pozvao u pomoć! Ako postoji pravac kojim Darko može presijeći debla tako da je zbroj duljina kraćih krajeva točno $k$, ispište ga, a ako Darku nema pomoći ispišite $-1$. Ako ih ima više, ispište onaj s najmanjom $y$ koordinatom.

Slika D.1 prikazuje rezanje iz prvog primjera zadatka

U prvom su retku prirodni brojevi $n$ ($1 ≤ n ≤ 10^5$) i $k$ ($1 ≤ k ≤ 10^9$) iz teksta zadatka.

U sljedećih $n$ redaka nalaze se brojevi $x_{1_i}$ $y_{1_i}$ $x_{2_i}$ $y_{2+i}$ ($1 ≤ x_{1_i} , y_{1_i} , x_{2_i} , y_{2_i} ≤ 10^9$, $x_{1_i} = x_{2_i}$) koji označavaju koordinate krajeva $i$-tog debla.

U jedinom retku potrebno je ispisati pravac s najmanjom $y$ koordinatom koji zadovoljava uvjet zadatka. Ako rješenje ne postoji ispišite $-1$. Vaše će se rješenje smatrati točnim ako je apsolutna i relativna pogreška manja od $10^{-5}$.