Title: Task: DIV
Author: klezmer ban
Last saved by: Slavi Marinov
Company: makefile co

Task: GAR          Country: BULGARIA
Garden

Day 1. Source file  gar.*		                Saturday 20-08-2005 Available memory: 32 MB. Maximum running time: 0.5 s.

Байтман притежава най-хубавата градина в Байтград. Той засадил n рози в градината. Дошло лятото и розите пораснали големи и красиви. Байтман разбрал, че няма да може да се грижи сам за цялата градина. Решил да наеме за помощници двама градинари. За целта Байтман иска за избере две правоъгълни области така, че всеки от градинарите да се грижи за розите в една от областите. Областите трябва да бъдат непресичащи се и всяка трябва да съдържа точно k рози.  

Байтман иска да направи огради, заграждащи правоъгълните области. Той няма достатъчно пари и затова би искал общата дължина на оградите да бъде минимална. Трябва да помогнете на Байтман да избере две правоъгълни области.

Градината е правоъгълник с дължина l метра и ширина w метра, като е разделена на lw квадрата, всеки със страна 1 метър. Разглеждаме координатна система с оси, успоредни на страните на градината, като долният ляв квадрат има координати (1,1), а горният десен – кординати (l,w). Всички квадрати имат целочислени координати (x,y), удовлетворяващи 1 ≤ x ≤ l  и 1 ≤ y ≤ w. Всеки квадрат може да съдържа произволен брой рози. 

Правоъгълните области трябва да бъдат избрани със страни, успоредни на координатните оси и върховете им да имат целочислени координати. За 1 ≤ l_1 ≤ l_2 ≤ l и 1 ≤ w_1 ≤ w_2 ≤ w правоъгълната област с върхове (l_1, w_1), (l_1, w_2), (l_2, w_1) и (l_2, w_2):
•	съдържа всички квадрати с координати (x, y), удовлетворяващи неравенствата   l_1 ≤ x ≤ l_2  и w_1 ≤ y ≤ w_2 
•	има периметър  2(l_2 – l_1 + 1) + 2(w_2 – w_1 + 1).

Двете правоъгълни области трябва да бъдат непресичащи се, т.е. да не съдържат общи квадрати. Даже, когато имат обща страна или общи части от страни, областите се заграждат с отделни огради.

Задача
Напишете програма, която
•	прочита от стандартния вход размерите на градината, броя на розите, броя на розите, които трябва да бъдат заградени във всяка от областите и координатите на розите;
•	намира две правоъгълни области, които имат минимална сума на периметрите и удовлетворяват дадените условия; 
•	извежда на стандартния изход минималната сума на периметрите на двете непресичащи се правоъгълни области, всяка съдържаща точно k рози, или думата NO, ако не съществуват такива области.

Вход
Първият ред на стандартния вход съдържа две цели числа l и w (1 ≤ l, w ≤ 250), отделени с един интервал – дължината и ширината на градината. Вторият ред съдържа две цели числа n и k (2 ≤ n ≤ 5000, 1 ≤ k ≤ n/2), отделени с един интервал – броят на розите в градината и броят на розите, които трябва да бъдат заградени във всяка от правоъгълните области. Във всеки един от следващите n реда са дадени по една двойка координати на поредната роза. Редът с номер i + 2  съдържа две цели числа l_i, w_i (1 ≤ l_i ≤ l, 1 ≤ w_i ≤ w), отделени с един интервал – координатите на квадрата, съдържащ i-тата роза. Възможно е в един квадрат да има две или повече рози. 

При 50% от тестовете размерите на градината ще удовлетворяват  l, w ≤  40.

Изход
Програмата трябва да изведе на единствен ред на стандартния изход едно цяло число – минималната сума на периметрите на двете непресичащи се правоъгълни области, всяка съдържаща точно k рози, или думата NO, ако не съществуват такива области.

Пример
За входните данни:	
6 5
7 3
3 4
3 3
6 1
1 1
5 5
5 5
3 1

правилният изход е:
22

Garden	/