Copying Books

Before the invention of printing, making even a single copy of a book was a hard job: every page had to be transcribed by hand by a scribe, and copying one book could take months. The only way to speed things up was to hire more scribes.

You have m books with (possibly different) page counts p1, p2, …, pm, and you want one copy of each. Divide the books among k scribes (k ≤ m). Each book is assigned to exactly one scribe, and every scribe must receive a contiguous run of books. That is, there exist increasing bounds 0 = b0 < b1 < b2 < … < bk = m such that the i-th scribe copies the books numbered bi-1 + 1 through bi.

The total time is determined by the scribe assigned the most pages, so you must choose the assignment that minimizes the maximum number of pages given to any single scribe. Find an optimal assignment.

The input consists of N cases. The first line contains the positive integer N. Each case then follows on exactly two lines. The first line contains two integers m and k (1 ≤ k ≤ m ≤ 500). The second line contains the page counts p1, p2, …, pm, separated by spaces. Every page count is positive and less than 100,000,000.

For each case, print exactly one line. Divide the sequence p1, p2, …, pm into exactly k parts so that the largest part sum is as small as possible. Separate the parts with a slash character /, and place exactly one space between any two successive numbers and between a number and a slash.

If several partitions achieve the smallest possible maximum, choose the one that minimizes the work of the first scribe, then of the second scribe, and so on. Every scribe must be assigned at least one book. Under this rule the answer is unique.