parchet

Meseria de parchetar a devenit mai uşoară de când a apărut parchetul laminat. Acesta se livrează în plăci pătratice de câte $1 \ \text{m} ^ 2$ şi montarea lui este destul de uşoară. Gigel este convins că este suficient de priceput să facă această operaţie în propria locuinţă. El dispune de planul locuinţei şi a cumpărat o anumită cantitate reprezentând $X \ \text{m} ^ 2$ de parchet laminat. Planul locuinţei este descris printr-un tablou bidimensional de dimensiuni $N \times M$, fiecare element al tabloului reprezentând exact $1 \ \text{m} ^ 2$.
Pereţii sunt reprezentaţi prin caracterul P iar suprafeţele camerelor prin caracterul S (spaţiu). În planul din figura următoare este descrisă o locuinţă cu $5$ camere acestea având respectiv, suprafeţele de $10, 2, 1, 3, 5 \ \text{m} ^ 2$.

Gigel nu este sigur de faptul că parchetul cumpărat îi ajunge. Din această cauză a hotărât iniţial să pună parchetul începând cu camera cea mai mare, apoi în următoarea, în ordinea descrescătoare a suprafeţei şi aşa mai departe, până în momentul în care parchetul rămas nu mai este suficient pentru acoperirea suprafeţei următoarei camere. Nu va lăsa neparchetată o cameră pentru a parcheta una cu o suprafaţă mai mică.
Gigel se mai gândeşte şi la posibilitatea de a acoperi complet un număr maxim de camere folosind întreaga cantitate de parchet.

Cerinţe

Fiind date $N$, $M$, $X$ şi planul locuinţei să se determine:

1. numărul $C$ de camere pe care a reuşit să le acopere Gigel şi numărul $R$ de $\text{m} ^ 2$ de parchet care îi rămân, procedând aşa cum a hotărât iniţial
2. numărul de posibilităţi de parchetare a unui număr maxim de camere, folosind întreaga cantitate de parchet

Date de intrare

Fişierul de intrare parchet.in conţine pe prima linie un număr natural $p$ reprezentând cerinţa care trebuie să fie rezolvată ($1$ sau $2$). Linia a doua a fişierului de intrare conţine numerele naturale $N$ şi $M$ separate printr-un spaţiu. Pe linia a treia se află numărul natural $X$. Următoarele $N$ linii conţin câte $M$ caractere P sau S descriind planul locuinţei.

Date de ieşire

Dacă valoarea lui $p$ este $1$, atunci fişierul de ieşire parchet.out conţine pe prima linie două numere naturale $C$ şi $R$ separate printr-un spaţiu, reprezentând respectiv numărul de camere acoperite cu parchet şi cantitatea de parchet rămasă, exprimată în $\text{m} ^ 2$.
Dacă valoarea lui $p$ este $2$, atunci pe prima linie a fişierului de ieşire se va scrie numărul de posibilităţi de parchetare a unui număr maxim de camere folosind întreaga cantitate de parchet, respectiv valoarea $0$ în cazul în care acest lucru nu este posibil.

Restricţii şi precizări

• $2 \leq N, M \leq 250$
• În casă sunt maxim $20$ de camere şi casa are pereţi spre exterior.
• Suprafaţa unei camere nu depăşeşte $(N - 2) \cdot (M - 2) \ \text{m} ^ 2$.
• Pentru rezolvarea corectă a cerinţei $1$ se acordă $50\%$ din punctaj, iar pentru rezolvarea corectă a cerinţei $2$ se acordă $50\%$ din punctaj.

Exemplul 1

parchet.in

1
7 9
19
PPPPPPPPP
PSSSPSPSP
PSSSPSPPP
PSSPPPPSP
PSPPSSPSP
PSPSSSPSP
PPPPPPPPP

parchet.out

3 1

Explicaţie

Se va rezolva doar cerinţa $1$.
Locuinţa are $5$ camere având suprafeţele de $10, 2, 1, 3, 5 \ \text{m} ^ 2$. Pot fi parchetate complet $3$ camere consumând $18 \ \text{m} ^ 2 = 10 + 5 + 3$. Rămâne $1 \ \text{m} ^ 2$ de parchet nefolosit.

Exemplul 2

parchet.in

2
7 9
19
PPPPPPPPP
PSSSPSPSP
PSSSPSPPP
PSSPPPPSP
PSPPSSPSP
PSPSSSPSP
PPPPPPPPP

parchet.out

1

Explicaţie

Se va rezolva doar cerinţa $2$.
Dacă se aleg camerele cu suprafeţele $10, 1, 3, 5$ va fi folosită întreaga suprafaţă de parchet. Există o singură posibilitate de a selecta un număr maxim de camere.