G. GCD of Strings
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Mohammad Nour and Marcel are close friends. One day Nour borrowed from Marcel some money.

After a few weeks, Nour decided to return the money to his friend, But unfortunately Marcel forgot how much it was. We all know that Nour is a funny person so he took advantage of this opportunity and decided to play with Marcel.

He gave him a huge number $$$a$$$, and asked him to split this number into at least $$$k$$$ numbers (parts), such that each digit belongs to exactly one part and each part contains no more than 9 consecutive digits

The $$$GCD$$$ of the numbers Marcel got after making the operation above is the amount of money Nour borrowed.

Marcel is a cunning, he wants the answer to be maximal possible, so help him to split the number $$$a$$$ such that the $$$GCD$$$ of its parts as big as possible.

The greatest common divisor, $$$GCD(a,b)$$$, of two positive integers $$$a$$$ and $$$b$$$ is the biggest integer that is a divisor of both $$$a$$$ and $$$b$$$.

Please note that: $$$GCD(0,x) = x$$$

Input

The first line of the input contains two integers $$$n$$$ and $$$k$$$ $$$(1 \le k \le {10^3}, 1 \le n \le {2 \times 10^3} )$$$ the length of $$$a$$$ and the minimum size of numbers Marcel should get.

The second line contains the number $$$a$$$ without leading zeros

Output

Print -1 if Marcel can't split the number according to the conditions above. Otherwise print the maximum amount of money he can get.

Examples
Input
8 2
63021002
Output
2
Input
9 3
303252015
Output
15
Input
3 4
150
Output
-1
Note

In the first test case, one of the optimal solutions is dividing the string into $$$630210$$$ and $$$02$$$ such that $$$GCD$$$ of them is $$$2$$$.

In the second test case, you can split the string into $$$30$$$, $$$32520$$$ and $$$15$$$.