Tăblițe

Alex este pasionat de istorie și de arheologie. În una dintre expedițiile lui, el a găsit $N$ tăblițe care conțineau numere naturale. Curios să afle despre originea lor, Alex l-a vizitat pe profesorul lui de istorie. Profesorul i-a spus băiatului că cele $N$ tăblițe sunt fragmente dintr-o veche inscripție geto-dacică. După ce le-au așezat în ordinea corectă, cei doi au reușit să reconstituiască inscripția prin concatenarea numerelor de pe tăblițe. De exemplu, dacă după ordonare tăblițele găsite de Alex conțin numerele $12$, $4$ și $1030$, atunci inscripția reconstituită va fi $1241030$.

Curios din fire, Alex vrea să analizeze fiecare secvență validă de $K$ cifre. O secvență este considerată validă dacă prima cifră din ea este nenulă. De exemplu, secvențele valide de $3$ cifre pentru inscripția $1241030$ vor fi, în ordine: $124$, $241$, $410$ și $103$, iar secvența $030$ nu este considerată validă, deoarece începe cu cifra $0$.

Cerințe

Alex vă roagă să îl ajutați să interpreteze rezultatele analizei și astfel să poată descifra secretul ascuns în inscripție.

1. Determinați numărul de secvențe valide pe care le va analiza Alex.
2. Determinați valoarea maximă a unei secvențe valide analizate și care este suma tuturor secvențelor valide analizate de Alex.

Date de intrare

Prima linie va conține trei numere naturale $C$, $N$ și $K$, unde $C$ reprezintă cerința care trebuie rezolvată, $N$ reprezintă numărul de tăblițe pe care le-a găsit Alex, iar $K$ reprezintă lungimea secvențelor de cifre care urmează să fie analizate. Pe următoarea linie se găsesc, separate prin câte un spațiu, $N$ valori, reprezentând numerele scrise pe tăblițe, după ordonarea lor.

Date de ieșire

• Dacă $C=1$, pe prima linie se va găsi un număr natural, reprezentând numărul de secvențe valide pe care le va analiza Alex.
• Dacă $C=2$, prima linie va conține două numere naturale, separate printr-un spațiu, reprezentând, în această ordine, valoarea maximă a secvenței analizată de Alex, respectiv suma valorilor secvențelor analizate de băiat.

Restricții și precizări

• $1 \leq C \leq 2$
• $1 \leq N \leq 10^5$
• $1 \leq K \leq 13$
• Valorile tăblițelor citite vor fi cuprinse între $1$ și $10^{18}$.
• Se garantează că inscripția conține minim $K$ cifre.
• Se garantează că răspunsul va intra pe tipul de date long long.

• Pentru 15 puncte, $C=1$ și toate cifrele de pe tăblițe sunt nenule.
• Pentru alte 15 puncte, $C=1$, fără alte restricții suplimentare.
• Pentru 20 de puncte, $C=2$ și toate cifrele de pe tăblițe sunt nenule.
• Pentru alte 50 de puncte, $C=2$, fără alte restricții suplimentare.

Exemplul 1

stdin

1 3 2
12 4 1030

stdout

5

Explicație

Se rezolvă cerința 1. Inscripția inițială era $1241030$, iar secvențele valide de lungime $2$ sunt $12$, $24$, $41$, $10$ și $30$. Prin urmare există $5$ secvențe valide de lungime $2$.

Exemplul 2

stdin

2 3 2
12 4 1030

stdout

41 117

Explicație

Se rezolvă cerința 2. Cea mai mare dintre secvențele valide este $41$, iar suma lor este $12 + 24 + 41 + 10 + 30 = 117$.

Exemplul 3

stdin

1 4 3
142 230 1420 5

stdout

8

Explicație

Se rezolvă cerința 1. Inscripția inițială era $14223014205$, iar secvențele valide de lungime $3$ sunt $142$, $422$, $223$, $230$, $301$, $142$, $420$ și $205$. Secvența $142$ este numărată de două ori, adică de fiecare dată când apare in inscripție. Deci sunt $8$ secvențe valide de lungime $3$.