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*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*7+1, a cărei valoare este 41.

Cerința

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 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 ≤ N < 1000
• 0 ≤ K ≤ 100
• 0 ≤ P ≤ 18, unde P este numărul operatorilor *
• N este număr impar
• Pentru 12 puncte, K = 0
• Pentru 17 puncte, P = 1 și K = 1
• Pentru 20 puncte, 1 ≤ K < P, 3 ≤ N < 40
• Pentru 32 puncte, 1 < P ≤ K, 41 ≤ N < 1000
• Pentru 19 puncte, 1 ≤ K < P, 41 ≤ N < 1000

Exemplul 1:

expresia.in

9 1
2*3+5+7+1

expresia.out

41

Explicație

Se efectuează o interschimbare între primul și cel de al treilea operator, obținând expresia 2+3+5*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

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