球球大作战
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65536/65536K (Java/Other)
Total Submission(s) : 16 Accepted Submission(s) : 9
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
小Z最近迷上了球球大作战，他准备出一个与球球大作战相似的题目来考考大家。现在有n个球依次排列在一条直线上，每个球有其对应的体积。每次合并操作可以将任意相邻两个球合并为一个球，合并之后的球的体积为这两相邻球体积之和。现在有m次合并，经过这m次合并之后，希望剩下球中体积的最小值能够最大(采用最佳合并策略)。
Input
输入一个T，代表数据的组数。（T<=10）
第二行包含两个正整数N,M，表示N个球，M次合并机会。
接下来一行为n个正整数x[1], x[2], … ,x[n]，其中x[i]表示编号为i的球的体积。
数据范围：1≤M<N≤100000，1≤x[i]≤100000。
第二行包含两个正整数N,M，表示N个球，M次合并机会。
接下来一行为n个正整数x[1], x[2], … ,x[n]，其中x[i]表示编号为i的球的体积。
数据范围：1≤M<N≤100000，1≤x[i]≤100000。
Output
对于每个测试样例，输出一行，包含一个整数，m次合并之后的剩下的球的体积的最小值最大是多少。每个测试样例占一行。
Sample Input
2 4 2 4 2 3 5 6 3 1 7 2 2 5 9
Sample Output
6
8
Hint：
第一组样例：
合并4、2得到{ 6 3 5 },合并3、5得到{ 6 8 }，最小值为6。
也可以这样进行合并，合并2、3得到{ 4 5 5 },合并4、5得到{ 9 5 }，最小值为5,但最小值小于上面的合并方案。
第二组样例：
合并1、7得到 { 8 2 2 5 9 }，合并2、2得到 { 8 4 5 9 }，合并4、5得到 { 8 9 9 }，最小值为8。Source
642超哥