This document is not available in English version.

III Obóz im. A. Kreczmara 2002

Zadanie: e
Autor: Tomasz Malesiński
E: Hetmany

dzień czwarty 9 sierpnia 2002
Plik źródłowy: e.??? (np. pas, c, cpp)
Plik wejściowy: e.in
Plik wyjściowy: e.out

Jak wiadomo hetman w szachach atakuje figury w ośmiu kierunkach (góra, dół, lewo, prawo i cztery kierunki ukośne) i nie może przeskakiwać przez zajęte pola, więc atakuje tylko pierwszą figurę w każdym kierunku. Dana jest szachownica, na której pewne pola są już zajęte przez inne figury. Należy tak poustawiać pewną liczbę hetmanów na wolnych polach, aby liczba par wzajemnie atakujących się hetmanów była największa. Bierzemy pod uwagę pary nieuporządkowane, tzn. pary różniące się tylko kolejnością uważamy za identyczne.

Zadanie

Napisz program, który:

Wejście

W pierwszym wierszu pliku e.in znajdują się cztery liczby całkowite pooddzielane pojedynczymi spacjami: w, h, n, m (3 <= w,h <= 7, 2 <= n <= wh-m, n <= 7, 0 <= m <= wh-2), oznaczające odpowiednio szerokość i wysokość szachownicy, liczbę hetmanów do ustawienia i liczbę zajętych pól. W następnych m wierszach są po dwie liczby całkowite xi i yi, 1 <= xi <= w, 1 <= yi <= h. Są to współrzędne (pozioma i pionowa) i-tego zajętego pola.

Wyjście

W pierwszym i jedynym wierszu pliku e.out powinna znaleźć się jedna liczba całkowita - maksymalna liczba par wzajemnie atakujących się hetmanów.

Przykład

Dla pliku wejściowego e.in:

4 5 5 2
2 2
2 5

poprawną odpowiedzią jest plik wyjściowy e.out:

8