Description

sf公司需要用无人机把 $n$ 件快递投放到不同的省。给定数组$a$，其中$a_i$表示第i 件快递的重量。由于安全限制,无人机在每次运输中的载重量为$M$。

公司计划在至多$k$次运输内完成所有快递的投放。为了提高效率,他们希望找到一个最小的可行的最大载重量$M$,使得所有快递都能按顺序在至多$k$次运输内投放完毕。

每次运输会从当前剩余快递的第一个开始,按顺序运送编号连续的一批快递。快递必须按原顺序运送,不能跳过或重新排序。

例如,假设$a= [1,3,2,4,3], k=3且M=6$,那么第一次运输选取前两个快递$[1,3,2]$ (总重量为6) ,第二次运输则选取$[4]$ (总重量为4) ,最后一次运输$[3]$ (总重量为3)。总共进行了$3$次运输,符合要求。若$M=5$,则无法在3次运输内完成所有快递的投放。

作为快递员中的智多星,你需要确定最小的整数M,以确保可以在至多$k$次运输内,完成所有快递的投放,且每次运输中投放的货物总重量之和不超过$M$。

Input

第一行包含一个正整数$T(1≤T≤10)$，表示数据组数；

对于每组数据有：

第一行包含两个正整数n,k，分别表示快递的数量和最多允许的运输次数。$(1≤n≤10^6，1≤k≤n)$

第二行包含n个正整数$a_1,a_2,a_3,……，a_n$，表示每件快递的重量$(1≤a_i≤10^9)$

Output

对于每组数据，输出一行，包含一个整数$M$，表示满足条件的最小的载重量

Samples

2
5 2
2 1 3 2 4
6 3 
3 5 1 6 2 4

6
8

Limitation

3s, 256MiB for each test case.