concurs "Bagae" | expresia

Dorel are o expresie aritmetică reprezentată ca un șir de caractere de lungime $N$, ce conține ca operanzi cifre nenule, iar ca operatori aritmetici adunarea și înmulțirea, operatori reprezentați prin + și *. Asupra expresiei aritmetice se pot efectua cel mult $K$ operații de interschimbare între doi operatori.

De exemplu, pentru expresia $2 \cdot 3 + 5 + 7 + 1$, a cărei valoare este $19$, dacă efectuăm o operație de interschimbare între primul și cel de-al treilea operator obținem expresia $2 + 3 + 5 \cdot 7 + 1$, a cărei valoare este $41$.

Cerință

Să se afle valoarea maximă a expresiei după efectuarea a cel mult $K$ operații de interschimbare între doi operatori.

Date de intrare

Fișierul de intrare expresia.in conține pe prima linie se află numerele $N$ și $K$, separate prin spațiu.

Pe cea de a doua linie se află expresia aritmetică.

Date de ieșire

Fișierul de ieșire expresia.out va conține o singură linie pe care se va afișa valoarea maximă a expresiei aritmetice.

Restricții și precizări

• $3 \leq N < 1000$
• $0 \leq K \leq 100$
• $0 \leq P \leq 18$, unde $P$ este numărul operatorilor *
• $N$ este număr impar

Exemplul 1

expresia.in

9 1
2*3+5+7+1

expresia.out

41

Explicație

Pentru primul exemplu, se efectuează o interschimbare între primul și cel de al treilea operator, obținând expresia $2+3+5 \cdot 7+1$ a cărei valoare este $41$.

Exemplul 2

expresia.in

19 2
2+4+1+5*3+9+1*6+1+7

expresia.out

157

Explicație

Pentru al doilea exemplu, se efectuează o interschimbare între al cincilea și al șaptelea operator, obținând expresia $2+4+1+5 \cdot 3 \cdot 9+1+6+1+7$ a cărei valoare este $157$.