23733번 - Subnumber Sum 다국어

Let's solve this simple problem.

Given a positive integer, we can make a new number by taking some digits from the given number and concatenating them without changing the order. Let's call it a subnumber of a given number. For example, we can take $3, 1, 1$ from $31415$ to make a subnumber $311$.

A positive integer of $N$ digits is given. You can make two subnumbers by selecting $K$ digits to make one and the remaining $N-K$ digits to make the other. Given the number of digits $K$ that you have to select, find the maximum sum of two subnumbers. It is allowed for a subnumber to have leading zeros.

The first line contains the number of test cases $T$ $(1 \leq T \leq 10,000)$. 

For each test case, the first line contains two integers $N, K$ $(2 \leq N \leq 18, 1 \leq K < N)$ and the second line contains a positive integer of $N$ digits. The input number has no leading zeros, although its subnumbers can.

For each test case, output the maximum sum of two subnumbers satisfying the conditions in one line.