Садок#286

Садок

1 секунда

64 мегабайти

Складна

Байтмен володіє найкрасивішим садом у Байттауні, де він посадив $n$ троянд. Настало літо, і квіти виросли великими й гарними. Байтмен зрозумів, що самостійно не зможе доглядати всі троянди, і вирішив найняти двох садівників на допомогу. Тому він має вибрати дві прямокутні ділянки, щоб кожен садівник доглядав троянди лише в межах своєї ділянки. Ділянки мають бути неперетинними, і кожна має містити рівно $k$ троянд.

Байтмен хоче обнести ці прямокутні ділянки парканом. Щоб заощадити гроші, паркан має бути якомога коротшим. Ваше завдання — допомогти Байтмену вибрати дві прямокутні ділянки.

Сад є прямокутником довжиною $l$ метрів і шириною $w$ метрів, поділеним на $l \cdot w$ l \cdot w одиничних квадратів розміром $1 \times 1$ 1 \times 1 метр. Вісь координат слід розташувати так, щоб вона була паралельна сторонам саду, й кожен квадрат мав цілі координати $(x, y)$ , де $1 \leq x \leq l$ 1 \le x \le l, $1 \leq y \leq w$ 1 \le y \le w. У кожному квадраті може бути будь-яка кількість троянд.

Вибрані прямокутні ділянки мають бути зі сторонами, паралельними сторонам саду, і їхні кути мають бути розташовані в квадратах з цілими координатами. Для $1 \leq l_{1} \leq l_{2} \leq l$ 1 \le l_1 \le l_2 \le l і $1 \leq w_{1} \leq w_{2} \leq w$ 1 \le w_1 \le w_2 \le w прямокутник з кутами $(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): - містить усі квадрати $(x, y)$ такі, що $l_{1} \leq x \leq l_{2}$ l_1 \le x \le l_2 та $w_{1} \leq y \leq w_{2}$ w_1 \le y \le w_2; - має периметр $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).

Два прямокутники мають бути неперетинними, тобто не можуть мати спільних квадратів. Навіть якщо вони мають спільний бік або його частину, їх треба обгородити окремими парканами.

Завдання

Напишіть програму, яка: - зчитує зі стандартного введення розміри саду, загальну кількість троянд, кількість троянд, які мають бути в кожній ділянці, і координати кожної троянди (квадрата, що її містить); - знаходить кути двох таких прямокутних ділянок із мінімально можливою сумою периметрів, які задовольняють усі наведені вище умови; - виводить мінімальну можливу суму периметрів двох неперетинних прямокутників, кожен з яких містить рівно $k$ троянд, або одне слово NO, якщо таких прямокутників не існує.

Вхідні дані

У першому рядку містяться два цілих числа $l$ і $w$ ( $1 \leq l, w \leq 250$ 1 \le l, w \le 250), розділені пробілом — довжина та ширина саду. У другому рядку — два цілих числа $n$ і $k$ ( $2 \leq n \leq 5000$ 2 \le n \le 5000, $1 \leq k \leq n /2$ 1 \le k \le n/2) — кількість троянд у саду та кількість троянд, які мають бути в кожному прямокутнику. У наступних $n$ рядках розташовані координати троянд, по одній у рядку. У $(i + 2)$ (i+2)-му рядку два цілих числа $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$ -ту троянду.

В одному квадраті може розташовуватись дві або більше троянд.

Вихідні дані

Виведіть у першому й єдиному рядку одне ціле число — мінімальну можливу суму периметрів двох неперетинних прямокутників, кожен з яких містить рівно $k$ троянд, або одне слово NO, якщо таких прямокутників не існує.

Приклади

Приклад 1