SP15963 HELPDONN - Help Donn

小明去参加了一个寻宝活动。 活动分为 $n$ 个阶段（编号 $1$ 到 $n$），小明必须按照由 $1$ 到 $n$ 的顺序参加。在寻宝的同时，他会用袋子装下这些宝藏。 在登记参加活动时，主办方会给他**至多** $k$ 个袋子。每一个袋子都可以承受任意大的重量，但每一个袋子最大承受的重量都应该相等。 在比赛开始后，小明就不允许换袋子了。在经历不同的阶段时，如果他的袋子不能再装当前阶段的宝藏时，他会将当前使用的袋子打包，交给工作人员，然后再拿出一个新的袋子，继续收集宝藏。 每个袋子的价钱与其可承受的最大重量成正比。小明想尽可能减少自己在购买袋子时所花的钱。 幸运的是，小明已经提前知道了每个阶段的宝藏重量。请你编写程序帮助他选择合适的袋子。

**本题中，单个测试点含有多组数据。** 每个测试点第一行输入整数 $T$，该测试点中包含的数据组数。 每组数据第一行输入两个整数 $n,k$，含义见题。 接下来 $n$ 行，每行一个整数，第 $i$ 行中的整数为第 $i$ 阶段中宝藏的重量。

对于每组数据，输出一行一个整数，表示每个袋子最小承受的重量。 ### 输入输出样例 #### 输入 #1 ``` 1 3 2 1 2 3 ``` #### 输出 #1 ``` 3 ``` #### 输入 #2 ``` 2 5 2 10 40 20 30 20 5 3 10 40 20 30 20 ``` #### 输出 #2 ``` 70 50 ``` #### 输入 #3 ``` 3 2 1 17 13 5 10 10 40 20 30 20 3 2 1 2 4 ``` #### 输出 #3 ``` 30 40 4 ```

#### 数据规模与约定 $1\le T\le 100$，$1\le n,k\le 1000$，宝藏的重量 $\le 1000$。