ŠIOM — Rožių sodas

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: garden.in

Rezultatų failas: garden.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Rožių sodas

Baitmenas turi puikų sodą. Jame pasodino n rožių. Atėjo vasara, gėlės užaugo didelės ir gražios. Baitmenas neįstengia vienas prižiūrėti visų rožių. Jis nusprendė pasamdyti du sodininkus ir nori sode parinkti dvi stačiakampes sritis – po vieną kiekvienam sodininkui. Kiekvienam sodininkui skiriama viena stačiakampė sritis. Stačiakampiai turi nesikirsti ir kiekviename turi būti lygiai po k rožių.

Aplink kiekvieną stačiakampį Baitmenas nori pastatyti tvorą, bet jis turi mažai pinigų, todėl tvora turi būti kiek galima trumpesnė. Jums reikia padėti Baitmenui išrinkti du stačiakampius.

Sodas yra l metrų ilgio ir w metrų pločio stačiakampis. Jis padalintas į $l\\timesw$ vienetinių kvadratų (1 metras $\\times$ 1 metras). Laikoma, kad koordinačių sistemos ašys lygiagrečios sodo kraštinėms. Visų kvadratų koordinatės yra sveikieji skaičiai (x, y), čia $1\\lex\\lel$ , $1\\ley\\lew$ . Kiekviename vienetiniame kvadrate gali augti bet kiek rožių.

Stačiakampiai turi būti parinkti taip, kad jų kraštinės būtų lygiagrečios sodo kraštinėms, o kampų koordinatės būtų sveikieji skaičiai. Stačiakampis, kurio kampų koordinatės ( $l_1$ , $w_1$ ), ( $l_1$ , $w_2$ ), ( $l_2$ , $w_1$ ) ir ( $l_2$ , $w_2$ ) (kai $1\\lel_1\\lel_2\\lel$ ir $1\\lew_1\\lew_2\\lew$ ):

apima visus kvadratus, kurių koordinatės (x, y) tenkina $l_1\\lex\\lel_2$ ir $w_1\\ley\\lew_2$ ir
turi perimetrą $2\\times(l_2-l_1+1)+2\\times(w_2-w_1+1)$ .

Du stačiakampiai laikomi nesikertančiais, jei jie neturi jokio bendro kvadrato. Jei jie turi bendrą kraštinę, tvoros vis vien statomos atskirai.

Parašykite programą, kuri rastų dviejų sąlygas tenkinančių stačiakampių, kurių perimetrų suma mažiausia, kampų koordinates.

Pradiniai duomenys

Pirmoje eilutėje pateikiami du sveikieji skaičiai: l ir w ( $1\\lel,w\\le250$ ). Tai sodo ilgis ir plotis. Antroje eilutėje yra du sveikieji skaičiai: n ir k ( $2\\len\\le5~000$ , $1\\lek\\len/2$ ). Tai bendras rožių skaičius sode ir reikalaujamas rožių skaičius kiekviename iš dviejų stačiakampių.

Tolesnėse n eilučių įrašytos rožių koordinatės, kiekvienai rožei skiriant po vieną eilutę. ( $i+2$ )-oje eilutėje yra du sveikieji skaičiai $l_i$ , $w_i$ ( $1\\lel_i\\lel$ , $1\\lew_i\\lew$ ) – kvadrato, kuriame yra i-toji rožė, koordinatės. Tame pačiame kvadrate gali būti dvi ir daugiau rožių.

Rezultatai

Rezultatas turi būti vienintelė eilutė, kurioje įrašytas lygiai vienas sveikasis skaičius – minimali dviejų nepersikertančių stačiakampių, kiekviename kurių auga po lygiai k rožių, perimetrų suma. Jei tokių stačiakampių poros neįmanoma rasti, spausdinamas vienintelis žodis NO.

Pavyzdys

Duomenys	Rezultatai
6 5 7 3 3 4 3 3 6 1 1 1 5 5 5 5 3 1	22

Šeštadieninė informatikos olimpiadininkų mokykla

Rožių sodas

Pradiniai duomenys

Rezultatai

Pavyzdys