工作时间

题目描述

Y 同学在新公司被分配了 $n$ 个任务。这些任务必须严格按照给定的顺序依次完成。

对于第 $i$ 个任务，Y 同学需要花费 $a_i$ 的时间才能做完。每个任务都必须使用一段连续的时间来处理，即一个任务只能在同一天内完成，绝对不能分割到两天或多天进行。此外，任务之间的顺序不能被打乱。

现在，上级要求 Y 同学必须在 $k$ 天内完成所有这 $n$ 个任务。由于 Y 同学希望每天能尽量少加班，他想知道在所有合法的任务分配方案中，单天最长工作时间的最小值是多少？

输入格式

本题有多组测试用例。

第一行输入一个整数 $T$，表示测试用例个数。

对于每组测试用例： 第一行包含两个整数 $n$ 和 $k$，分别表示任务的数量和要求完成的天数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示完成每个任务所需的时间。

输出格式

对于每组测试用例，输出一行一个整数，表示 Y 同学单天最长工作时间的最小值。

样例

样例输入 #1

3
8 1
4 7 6 9 8 1 8 3 
4 2
10 3 10 1 
4 3
10 7 2 9 

样例输出 #1

46
13
10

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le T \le 1000$
• $1 \le n \le 10^5$
• $1 \le k \le 10^9$
• $1 \le a_i \le 10^9$
• 所有测试用例中 $n$ 的总和满足 $\sum n \le 2 \times 10^5$。