Bağça#286

Bağça

1 saniyə

64 meqabayt

Çətin

Byteman Bytetownda ən gözəl bağa sahibdir və o, bağında $n$ ədəd qızılgül əkib. Yay gəlib, çiçəklər böyük və gözəl olublar. Byteman başa düşür ki, artıq bütün qızılgüllərə təkbaşına qulluq edə bilmir və ona görə də iki bağban işə götürməyə qərar verir. Deməli, o, iki düzbucaqlı sahə seçməlidir ki, hər bir bağban bir sahədəki qızılgüllərə qulluq etsin. Sahələr üst-üstə düşməməli və hər birində dəqiq $k$ ədəd qızılgül olmalıdır.

Byteman bu düzbucaqlı sahələrin ətrafına hasar çəkmək istəyir. Puluna qənaət etmək üçün hasar mümkün qədər qısa olmalıdır. Səndən xahiş olunur ki, Bytemana bu iki düzbucaqlı sahəni düzgün seçməyə kömək edəsən.

Bağ $l$ metr uzunluğunda və $w$ metr enində düzbucaqlıdır və $l \cdot w$ l \cdot w sayda, hər biri $1 \times 1$ 1 \times 1 metr ölçülü vahid kvadratlara bölünüb. Koordinat oxlarının bağın kənarlarına paralel çəkildiyini təsəvvür edin, belə ki, bütün kvadratların koordinatları $(x, y)$ kimi tam ədədlərdir, burada $1 \leq x \leq l$ 1 \le x \le l, $1 \leq y \leq w$ 1 \le y \le w. Hər kvadratda istənilən sayda qızılgül ola bilər.

Seçilən düzbucaqlı sahələrin kənarları bağın kənarları ilə paralel olmalı, künc nöqtələrinin koordinatları tam ədəd olmalıdır. $1 \leq l_{1} \leq l_{2} \leq l$ 1 \le l_1 \le l_2 \le l və $1 \leq w_{1} \leq w_{2} \leq w$ 1 \le w_1 \le w_2 \le w olduqda, küncləri $(l_{1}, w_{1})$ (l_1, w_1), $(l_{1}, w_{2})$ (l_1, w_2), $(l_{2}, w_{1})$ (l_2, w_1), $(l_{2}, w_{2})$ (l_2, w_2) olan düzbucaqlı: - bütün $(x, y)$ kvadratlarını əhatə edir, burada $l_{1} \leq x \leq l_{2}$ l_1 \le x \le l_2 və $w_{1} \leq y \leq w_{2}$ w_1 \le y \le w_2; - perimetri $2 \cdot (l_{2} - l_{1} + 1) + 2 \cdot (w_{2} - w_{1} + 1)$ 2 \cdot (l_2 - l_1 + 1) + 2 \cdot (w_2 - w_1 + 1)-ə bərabərdir.

Hər iki düzbucaqlı sahə üst-üstə düşməməlidir, yəni ümumi heç bir kvadratı olmamalıdır. Hətta kənar və ya bir hissə ortaq olsa belə, ayrıca hasarla əhatə olunmalıdırlar.

Tapşırıq

Proqram yazın ki: - standart girdidən bağın ölçülərini, qızılgüllərin ümumi sayını, hər düzbucaqlı sahədə olmalı qızılgüllərin sayını və hər bir qızılgülün koordinatını oxusun; - yuxarıdakı şərtləri ödəyən, üst-üstə düşməyən iki düzbucaqlı sahənin künclərini və perimetrlərinin cəmini minimum edən variantları tapsın; - hər iki düzbucaqlı sahənin perimetrlərinin minimum cəmini, yəni cavabı çap etsin, əgər belə düzbucaqlı sahələr mümkün deyilsə, tək bir **NO** sözünü yazsın.

Giriş

İlk sətirdə iki tam ədəd $l$ və $w$ ( $1 \leq l, w \leq 250$ 1 \le l, w \le 250) var — bağın uzunluğu və eni. İkinci sətirdə iki tam ədəd $n$ və $k$ ( $2 \leq n \leq 5000$ 2 \le n \le 5000, $1 \leq k \leq n /2$ 1 \le k \le n/2) — bağdakı qızılgüllərin sayı və hər düzbucaqlı sahədə olmalı qızılgüllərin sayı. Növbəti $n$ sətirin hər birində bir qızılgülün yerləşdiyi kvadratın koordinatları var. $(i + 2)$ (i+2)-ci sətirdə $l_{i}, w_{i}$ l_i, w_i ( $1 \leq l_{i} \leq l$ 1 \le l_i \le l, $1 \leq w_{i} \leq w$ 1 \le w_i \le w) — $i$ -ci qızılgülün yerləşdiyi kvadratın koordinatları var.

Bir kvadratda bir neçə qızılgül ola bilər.

Çıxış

Yeganə sətirdə — üst-üstə düşməyən iki düzbucaqlı sahənin minimum perimetr cəmini çap edin. Əgər belə düzbucaqlı sahələr yoxdursa, tək bir **NO** sözünü çap edin.

Nümunələr

Nümunə 1