tablou

Se consideră un tablou cu N linii și N coloane (numerotate de la $1$ la $N$) care conține valoarea $1$ în fiecare dintre cele $N \cdot N$ celule. Valorile din tablou pot fi modificate prin aplicarea a două operații codificate astfel:

• $L \ nr$, prin care se schimbă simultan toate semnele numerelor din linia cu numărul $nr$.
• $C \ nr$, prin care se schimbă simultan toate semnele numerelor din coloana cu numărul $nr$.

Cerință

1. Dându-se o succesiune de $K$ operații ($L \ nr$ sau $C \ nr$) asupra liniilor/coloanelor tabloului inițial (în care toate celulele conțin valoarea $1$) să se determine numărul valorilor pozitive din tablou la finalul executării celor $K$ operații.
2. Să se determine numărul minim de operații $L \ nr$ sau $C \ nr$, care, aplicate tabloului inițial, îl modifică astfel încât tabloul obținut să conțină exact $Z$ valori negative.

Date de intrare

Fișierul de intrare tablou.in conține pe prima linie numărul $p = 1$ sau $p = 2$, reprezentând numărul cerinței ce trebuie rezolvată.

• Dacă $p = 1$ atunci linia a doua a fișierului de intrare conține numerele $N$ și $K$, separate printr-un spațiu, iar următoarele $K$ linii conțin fiecare câte o literă mare ($L$ sau $C$) și un număr $nr$, separate printr-un spațiu, reprezentând codificarea uneia dintre cele două operații ($L \ nr$ sau $C \ nr$).
• Dacă $p = 2$ atunci linia a doua a fișierului de intrare conține numerele $N$ și $Z$, separate printr-un spațiu.

Date de ieșire

• Dacă $p = 1$, atunci fișierul de ieșire tablou.out conține pe prima linie un număr natural, reprezentând numărul valorilor pozitive din tabloul obținut la finalul executării celor $K$ operații asupra tabloului inițial (răspunsul la cerința $1$).
• Dacă $p = 2$, atunci fișierul de ieșire tablou.out conține pe prima linie un număr natural reprezentând numărul minim de operații $L \ nr$ sau $C \ nr$, care, aplicate tabloului inițial, îl modifică astfel încât tabloul obținut să conțină exact $Z$ valori negative (răspunsul la cerința $2$). Dacă prin aplicarea de operații $L \ nr$ sau $C \ nr$ tabloului inițial nu se poate obține un tablou cu $Z$ valori negative, atunci, fișierul va conține pe prima linie valoarea $0$ (zero).

Restricții și precizări

• $N, K, Z$ și $nr$ sunt numere naturale
• $3 \leq N \leq 20 \ 000$; $1 \leq K \leq 43 \ 000$; $1 \leq Z \leq N \cdot N$; $1 \leq nr \leq N$;
• Prin schimbare de semn, valoarea $-1$ se transformă în $1$ și valoarea $1$ se transformă în $-1$
• Se acordă $10$ puncte din oficiu și câte $45$ de puncte pentru rezolvarea corectă a fiecărei cerințe.

Exemplul 1

tablou.in

1
4 4
L 1
L 3
C 1
L 1

tablou.out

10

Explicație

$N = 4$. La finalul aplicării succesiunii de $K = 4$ operații, tablou modificat are conținutul:

-1  1  1  1
-1  1  1  1
 1 -1 -1 -1
-1  1  1  1

Astfel, tabloul conține $10$ valori pozitive.

Exemplul 2

tablou.in

2
3 5

tablou.out

3

Explicație

Sunt necesare minimum $3$ operații, de exemplu:

$L \ 3$
$L \ 1$
$C \ 1$

Exemplul 3

tablou.in

2
4 7

tablou.out

0

Explicație

Nu există nicio succesiune de operații pentru care să se obțină $Z = 7$ valori negative.