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.
Cerinta
Ajutati-l pe Gigel sa gaseasca
numarul de posibilitati in care se pot aseza cele K
ture.
Date de intrare
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.
Date de iesire
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.
Restrictii
0 <= N*M <= 250
0 <= K <= 100
0 <= P <= N*M
Exemplu
ture.in
ture.out
3 3 3
1
2 2
4
Diaconu Adrian Paul
Universitatea Bucuresti,
Facultatea de Matematica si Informatica