• Transport

 

 

时间限制:3s

空间限制:512MB

 

题目描述

 

有n个货物,要把他们从A地运送到B地,每一个货物都有自己的重量。可以使用一个最多能装重量为C的货物的车来运输它们。

每一轮运输,运输者每次选出一个当前这辆车上可以装运的重量最大的货物,直到不存在这样的货物为止。

现在运输者希望用不超过K轮运输将所有货物运送到B地。他想知道C的最小值为多少。

 

输入格式

 

本题包含多组输入。

每组输入的第一行包含两个整数n,K,其含义见题目描述。

每组输入的第二行包含n个整数,第i个整数w_i表示第i个货物的重量。

 

输出格式

 

对于每组输入,输出一行一个整数,表示C的最小值。

 

样例输入

 

2

10 3

17 16 10 10 9 8 8 7 6 5

10 3

170 161 100 100 90 80 80 80 60 59

 

样例输出

 

32

330

 

数据范围

 

对于30%的数据,1<=n<=20。

对于100%的数据,1<=n,k<=2,000,w_i<=2,000,T<=10。