The Scribers

Time Limit: 1 sec

 

The Problem

Once upon a time there is no Xerox. So copying document was one of the most difficult jobs .Once in a rural area of Bangladesh there lived a guy named Arafat who had the business of copying books ,documents or so . He had a small shop and there were some scribers who worked there with daily wages .The scriber is the guy who rewrites a document or so. One day a work order came from guy. Some books have to be re written. There have m books (numbered 1, 2 ... m) that may have different number of pages (p₁, p₂ ... p_m) and the guy want to make one copy of each of them.

The task is to divide these books among k scribers of Arafat’s shop, k <= m. Each book can be assigned to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numbers 0 = b₀ < b₁ < b₂, .< b_k-1 <= b_k = m such that i-th scriber gets a sequence of books with numbers between b_i-1+1 and b_i. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore, your goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment.

 

The Input

The input consists of N cases (equal to about 200). The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly two lines. At the first line, there are two integers m and k, 1 <= k <= m <= 500. At the second line, there are integer’s p₁, p₂, p_m separated by spaces. All these values are positive and less than 10000000.

 

The Output

For each case, print exactly one line. The line must contain the input succession p₁, p₂,.... p_m divided into exactly k parts such that the maximum sum of a single part should be as small as possible. Use the slash character ('/') to separate the parts. There must be exactly one space character between any two successive numbers and between the number and the slash.

If there is more than one solution, print the one that minimizes the work assigned to the first scriber, then to the second scriber etc. But each scriber must be assigned at least one book.

 

Sample Input

1

5 3

100 200 300 400 500

 

Sample Output

100 200 300 / 400 / 500

 

 

 

Online Mock Contest 2016

Problem Setter: Parag Paul