ture

Gigel are o tabla de sah cu N linii si M coloane. El vrea sa aseze pe tabla K ture astfel incat acestea sa nu se atace intre ele (consideram ca doua ture se ataca daca ele se afla pe aceeasi linie sau pe aceeasi coloana). Pentru a face lucrurile mai interesante, Gigel a marcat anumite casute in care nu poate aseza nici o tura si acum vrea sa stie in cate moduri poate aseza turele.

Pe prima linie a fisierului de intrare ture.in sunt scrise trei numere naturale N, M si K separate prin cate un spatiu. Pe cea de-a doua linie se afla P numarul de casute marcate de Gigel. Urmeaza apoi P linii cu cate doua numere x, y cu semnificatia ca Gigel a marcat casuta de pe linia x si coloana y.

Fisierul de iesire ture.out va contine o singura linie pe care va fi scris numarul de posibilitati de amplasare a turelor pe tabla de sah.

• 0 <= N*M <= 250
• 0 <= K <= 100
• 0 <= P <= N*M

ture.in	ture.out
3 3 3 1 2 2	4

Timp maxim de executie/test: 0.3 secunde

Diaconu Adrian Paul
Universitatea Bucuresti, Facultatea de Matematica si Informatica
ditzone@gmail.com