|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||512 MB||0||0||0||0.000%|
Little Max's most favorite activities are eating sweets and solving difficult mathematical riddles. The boy is happy when he finds a puzzle on a candy wrapper, which is a set of non-negative integers that he needs to sum up. Unfortunately, all the numbers on the wrapper are stuck together so that Max can't understand where one number ends, and where the next one starts.
The boy remembers that there are always exactly $k$ numbers on a wrapper, none of them containing leading zeros. He decided to split this string of digits into numbers on his own. He just needs to insert $k - 1$ delimiters into the string. Max wants to get the most interesting puzzle, the one that has the maximum possible result.
Your task is to find the maximum total sum of $k$ numbers that Max can get by splitting given string.
The first line contains two integers $n$ and $k$ --- the number of digits in the string on the wrapper and the number of integers, in which string must be split ($1 \le k \le n \le 5 \cdot 10^5$).
The second line contains a string of $n$ decimal digits.
It's possible to split the string into integers without any leading zero.
Output single integer --- maximum possible result.
$n \le 9$
$n \le 100$
$n \le 1\,000$
$n \le 5 \cdot 10^5$
3 2 528
4 3 9050
5 3 07800
In the first sample input splitting with the maximum sum is 52, 8;
In the second sample input splitting with the maximum sum is 90, 5, 0;
Consider all splitting for the third sample input:
Thus a splitting with the maximum sum is 0, 7, 800.