Un nou joc este din ce în ce mai popular în cercurile militare de pe planeta Algorithm. Jocul presupune existenţa a doi jucători, a unei foi de hârtie de matematică şi a unor jetoane (numite în cele ce urmează soldaţi). Primul jucător desenează pe o foaie de hârtie de matematică un dreptunghi (având lăţimea m şi lungimea n). Unele dintre pătrăţelele dreptunghiului sunt colorate în negru, iar altele sunt necolorate. Se spune că acel dreptunghi este ţara primului jucător, iar pătrăţelele negre sunt mlaştini. De asemenea, primul jucător asociază fiecărei coloane şi, respectiv, fiecărei linii de pătrăţele din ţara sa o valoare (pentru coloana j se asociază o valoare Cj, oricare ar fi j=1, 2, ..., n, iar pentru linia i se asociază o valoare Li, oricare ar fi i, i=1, 2, ..., m). Ţara se consideră cucerită dacă se pot dispune soldaţi în pătrăţelele necolorate (maxim un soldat pe pătrat), astfel încât pe linia i să fie minim Li soldaţi, iar pe coloana j să fie minim Cj soldaţi, pentru orice i şi j. Cel de-al doilea jucător se uită la desen şi la valorile corespunzătoare liniilor şi coloanelor şi trebuie să spună un număr T de soldaţi cu care se poate ocupa ţara, sau să spună că ţara este invulnerabilă. Jocul este câştigat de primul jucător dacă există un număr A<T, astfel încât ţara să poata fi ocupată cu A soldaţi, sau dacă al doilea jucător a spus că ţara este invulnerabilă şi nu era aşa. Cel de-al doilea jucător câştigă în restul cazurilor.

Cerinţă

Generalul Cormen-Knuth şi-a dat seama că există întotdeauna o strategie de câştig pentru cel de-al doilea jucător. El vă cere, obişnuit fiind să nu facă nimic personal ci doar să dea ordine, să faceţi un program care, primind ca intrare desenul unei ţări, să găseascăe numărul minim T de soldaţi cu care se poate ocupa respectiva ţară, dacă aceasta poate fi cucerită, sau să afirme că e invulnerabilă. Generalul este extrem de dur, aşa că o greşeală va fi penalizată drastic.

Date de intrare

Fişierul de intrare joc4.in conţine pe prima linie trei numere naturale separate prin spaţii m n k, care reprezintă numărul de linii şi numărul de coloane ale ţării, respectiv numărul de mlaştini din ţară. Pe cea de a două linie se află m numere naturale separate prin spaţii L1, ..., Lm, unde L_i reprezintă numărul minim de soldaţi care trebuie să se afle pe linia i astfel încât ţara să fie ocupată. Pe cea de a treia linie se află n numere naturale separate prin spaţii C1, ..., Cn , unde Cj reprezintă numărul minim de soldaţi care trebuie să se afle pe coloana j astfel încât ţara să fie ocupată. Pe fiecare dintre următoarele k linii se află câte două numere naturale separate prin spaţiu X Y (1≤X≤m, 1≤Y≤n), reprezentând coordonatele pătrăţelelor negre (mlaştini).

Date de ieşire

Fişierul de ieşire joc4.out va conţine o singură linie pe care va fi scris numărul minim T de soldaţi cu care poate fi ocupată ţara sau mesajul INVINCIBILA, dacă ţara nu poate fi ocupată.

Restricţii

1 ≤ n, m ≤ 200
0 ≤ k ≤ n*m

Exemple

joc4.in	joc4.out
4 4 4 1 1 1 1 0 1 0 3 1 4 2 2 3 3 4 3	4
4 4 4 1 1 1 1 1 1 1 1 1 1 1 2 1 3 1 4	INVINCIBILA

autor: Emilian Miron

propunător: Prof. Emanuela Cerchez

Liceul de Informatica ″Grigore Moisil″

emanuela.cerchez@gmail.com