J4 习题-5 木材加工

题目描述

某工厂有 $n$ 个独立的作业，由 $m$ 台相同的机器进行加工处理。作业 $i$ 所需的加工时间为 $t_i$，任何作业在被处理时不能中断，也不能进行拆分处理。现厂长请你给他写一个程序：算出 $n$ 个作业由 $m$ 台机器加工处理的最短时间。

输入格式

第一行 $T$ ，表示有 $T$ 组测试数据；

每组测试数据的第一行分别是整数 $n,m$，接下来的一行是 $n$ 个整数 $t_i$。

输出格式

所需的最短时间。

样例输入

2
2 2
1 5
6 3
2 5 13 15 16 20

样例输出

5
28

样例分析

样例中的第二组数据，第三个任务和第四个任务安排在一台机器，第二个任务和第五个任务安排在一台机器，第一个任务和第五个任务安排在一台机器，能获得完成所有任务的最短时间。

数据范围

对于$100\%$ 的数据：$1<T \le 100$ , $1 \le n \le 10000$，$1 \le m \le 100$ ， $1 \le t \le 100$。