책 나눠 베끼기

인쇄술이 발명되기 전에는 책을 한 부 베껴 쓰는 일조차 매우 힘들었습니다. 모든 내용을 필경사가 손으로 옮겨 적어야 했고, 한 권을 베끼는 데 몇 달이 걸리기도 했습니다. 작업을 빠르게 하는 유일한 방법은 필경사를 더 많이 고용하는 것이었습니다.

이제 m권의 책이 있고, 각 책은 서로 다른 쪽수 p1, p2, …, pm을 가질 수 있습니다. 이 책들을 k명의 필경사에게 나누어 각각 한 부씩 베끼려 합니다(k ≤ m). 한 권은 정확히 한 명에게만 배정되며, 각 필경사는 번호가 연속된 책들만 맡아야 합니다. 즉 0 = b0 < b1 < b2 < … < bk = m을 만족하는 증가하는 경계값들이 존재하여, i번째 필경사는 번호가 bi-1 + 1부터 bi까지인 책들을 맡습니다.

전체 작업 시간은 가장 많은 분량을 맡은 필경사에 의해 결정됩니다. 따라서 한 명의 필경사가 맡는 쪽수의 최댓값을 최소화하도록 배정해야 합니다. 최적의 배정을 구하세요.

입력은 N개의 테스트 케이스로 이루어집니다. 첫 줄에는 양의 정수 N이 주어집니다. 이어서 각 케이스가 주어지며, 한 케이스는 정확히 두 줄로 구성됩니다. 첫 줄에는 두 정수 m과 k가 주어집니다(1 ≤ k ≤ m ≤ 500). 둘째 줄에는 각 책의 쪽수 p1, p2, …, pm이 공백으로 구분되어 주어집니다. 모든 쪽수는 양수이며 100,000,000보다 작습니다.

각 케이스마다 정확히 한 줄을 출력합니다. 입력으로 주어진 수열 p1, p2, …, pm을 정확히 k개의 부분으로 나누되, 한 부분의 쪽수 합의 최댓값이 가능한 한 작아지도록 합니다. 각 부분은 슬래시 문자 /로 구분하며, 인접한 두 수 사이와 수와 슬래시 사이에는 항상 공백을 정확히 하나만 둡니다.

최댓값을 최소로 하는 방법이 여러 가지라면, 첫 번째 필경사의 분량이 가장 작아지는 것을, 그다음에는 두 번째 필경사의 분량이 가장 작아지는 것을, 이런 식으로 선택합니다. 단, 모든 필경사는 최소 한 권 이상을 맡아야 합니다. 이 규칙에 따라 답은 유일하게 결정됩니다.