sss

Se dă un număr $N$, și un șir de $N$ numere naturale nenule.

Cerință

1. Determinați suma valorilor aflate pe ultimele $K$ poziții în șir (unde $K$ reprezintă valoarea celei mai din dreapta cifre nenule a primei valori din șir).
2. Ne imaginăm împărțirea șirului în secvențe în următorul mod: prima secvență este formată din primele $L$ elemente, a doua este formată din următoarele $L - 1$ elemente, a treia este formată din următoarele $L - 2$ elemente și așa mai departe, ultima secvență este formată dintr-un singur element și acesta coincide cu ultimul element din șir. Considerând suma valorilor fiecărei secvențe, să se determine cea mai mare dintre aceste sume.

Date de intrare

Pe prima linie a fișierului sss.in se află două valori $C$ și $N$ separate printr-un spațiu. Pe linia a doua se află $N$ numere naturale separate prin câte un spațiu. Pentru $C = 1$ se rezolvă doar cerința $1$ iar pentru $C = 2$ se rezolvă doar cerința $2$.

Date de ieșire

Fișierul sss.out conține un singur număr care reprezintă valoarea calculată conform cerinței.

Restricții și precizări

• $1 \leq n \leq 100 \ 000$;
• Valorile din șir sunt numere naturale nenule $\leq 100 \ 000$;
• Se garantează că pentru testele în care $C = 1$ șirul are cel puțin $K$ elemente;
• Se garantează că valoarea lui N permite descompunerea conform descrierii, pentru testele care au $C = 2$;
• Pentru teste în valoare de $51$ de puncte avem $C = 1$;
• Pentru $27$ de puncte dintre testele în care $C = 1$, primul număr din șir are o cifră;
• Pentru teste în valoare de $49$ de puncte avem $C = 2$;
• Pentru teste în valoare de $22$ de puncte dintre cele care au $C = 2$, valoarea lui $N$ este mai mică sau egală cu $10$.
• Denumirea problemei este o prescurtare de la “sume și secvențe”.

Exemplul 1

sss.in

1 6
120 4 21 5 31 6

sss.out

37

Explicație

Ultima cifră nenulă a primului element din șir este $2$. Suma ultimelor două valori din șir este $37$.

Exemplul 2

sss.in

2 10
1 4 2 1 3 6 1 6 5 3

sss.out

11

Explicație

Descompunerea se poate realiza în secvențe de lungimile $4$, $3$, $2$ și $1$. Sumele obținute pentru fiecare sunt: $8$, $10$, $11$, $3$.