26300번 - Hrabro Hvalisanje 다국어

Dolazi teška zima. Grijanje na plin postaje sve skuplje, alternativa su drva. Stoga, Mirko i Slavko cijepaju drva i rade pripreme za zimu. Nakon sat vremena rada, odlučili su uzeti kratak predah. Sjede oni tako u tišini, piju vodu, kaže Mirko da ublaži dosadu:

“Slavko, mogu jedinim udarcem sjekire udariti tri cjepanice.”

Slavko digne obrve, namrgodi usne pa reče: “Ha, meni se čini da bih ja mogao barem šest ili sedam.”

Vi gledate sa strane taj razgovor i vrlo rado bi htjeli izjaviti neku rečenicu oblika: “Dečki, slabo je to, ja mogu jednim udarcem sjekire udariti točno c cjepanica.” te im zatim pokazati kako se to radi. Međutim, vaš problem je da prvo trebate odrediti najveći mogući c za koji to vrijedi.

Cjepanice u ovom zadatku možemo zamisliti kao pravokutnike kojima su stranice paralelne koordinatnim osima, a sjekiru možemo zamisliti kao dužinu duljine l.

Odredite najveći mogući c takav da postoji dužina duljine l koja ima neprazan presjek s točno c pravokutnika.

U prvom su retku prirodni brojevi n (1 ≤ n ≤ 15) i l (1 ≤ l ≤ 1 000), broj cjepanica i duljina sjekire.

U sljedećih su n redaka po četiri cijela broja x₁, y₁, x₂, y₂ (0 ≤ x₁ ≤ x₂ ≤ 1 000), (0 ≤ y₁ ≤ y₂ ≤ 1 000), donji-lijevi kut (x₁, y₁) i gornji-desni kut (x₂, y₂) i-te cjepanice.

Traženi broj c iz teksta zadatka.

Pojašnjenje probnog primjera: