Maximum Product

Problem Description

The year 2000 was designated as the "World Mathematical Year" by the International Mathematical Union, and it also marks the 90th anniversary of the birth of the famous Chinese mathematician Hua Luogeng. In his hometown Jintan, Jiangsu, a math competition was organized. Your good friend XZ was lucky to participate. The host gave all contestants the following problem:

Given a digit string of length $N$, the contestant must insert $K$ multiplication signs to split it into $K+1$ parts, and find a way to maximize the product of these $K+1$ parts.

To help contestants understand, the host gave the following example:

For the digit string $312$, when $N=3,K=1$, there are two ways:

• $3 \times 12 = 36$
• $31 \times 2 = 62$

The result satisfying the requirement is $31 \times 2 = 62$.

Now, please help your good friend XZ design a program to find the correct answer.

Input Format

The input has two lines:

The first line contains two natural numbers $N,K$.

The second line is a digit string of length $N$.

Output Format

Output the maximum product (a natural number) found.

Sample Input 1

4 2
1231

Sample Output 1

62

Constraints

For $60\%$ of the test data, $6\le N\le 20$. For all test data, $6\le N\le 40,\ 1\le K\le 6$.