Description

The year 2000 was designated as the World Year of Mathematics by the International Mathematical Union, and it also marked the 90th birth anniversary of the renowned Chinese mathematician Hua Luogeng. In Jintan, Jiangsu, Hua Luogeng’s hometown, a special mathematics contest was held. Your good friend XZ participated, and the host posed the following problem:

Given a numeric string of length $N$, insert $K$ multiplication signs to split it into $K + 1$ parts. Find a way to split it so that the product of these $K + 1$ parts is maximized.

To help participants understand the problem, the host gave the following example:

Given the numeric string $312$, when $N = 3, K = 1$, there are two ways to split it:

1. $3 \times 12 = 36$.
2. $31 \times 2 = 62$.

In this case, the correct result is $31 \times 2 = 62$.

Now, please help your friend XZ write a program to compute the correct answer.

Input Format

The input consists of two lines:

• The first line contains two natural numbers $N, K$.
• The second line contains a numeric string of length $N$.

Output Format

Output the maximum product (a natural number) corresponding to the given input.

4 2
1231

62

Hint

Constraints

• For $60\%$ of the testdata: $6 \le N \le 20$.
• For all testdata: $6 \le N \le 40$, $1 \le K \le 6$.

Translated by ChatGPT 5