1417 : 数列划分

Description

给一个有 \(n\) 个正整数的序列，连续地将其分为互不重叠的 \(k\) 份，即每一份都是该序列的一个子串，不能调换顺序。

求一个划分方案，使数字之和最大的那一份，其和在所有划分方案里最小。

Input

每组数据第一行两个整数 \(n, k\)，其中\(1\leq k \leq n \leq 10^5\)。

第二行 \(n\) 个不大于 \(1000\) 的正整数。

Output

求划分 \(k\) 份让数字之和最大那一份的和最小的方案，在划分位置标注 “/”，与数字用空格隔开。

如果有多种方案，输出第一个块最小的方案，如果依然多种，则第二个块最小，依此类推。

Sample

9 3
10 20 30 40 50 60 70 80 90

10 20 30 40 50 / 60 70 / 80 90

Hint

Source

Author

CSGrandeur