题目描述

何老师需要在接下来的 $m$ 天中完成 $n$ 个章节的备课。

章节必须按照原来的顺序准备。每天至少准备一个章节，并且同一天准备的章节必须是连续的一段。每个章节只能准备一次，全部章节都必须完成。

第 $i$ 个章节的备课工作量为 $a_i$。一天的工作量等于当天准备的所有章节的工作量之和。

为了避免某一天过于劳累，何老师希望合理安排每天准备的章节，使工作量最大的一天尽可能轻松。

请计算在最优安排下，单日最大工作量的最小值。

输入

第一行一个正整数 $T$（$1 \leq T \leq 5$），表示测试组数。

对于每组数据：

第一行两个正整数 $n,m$（$1 \leq m \leq n \leq 10^5$），表示章节数量和备课天数。

第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_i \leq 10^9$），表示每个章节的工作量。

所有测试组的 $n$ 之和不超过 $2 \times 10^5$。

输出

对于每组数据，输出一行一个整数，表示单日最大工作量的最小值。

样例 #1

样例输入#1

1
5 3
1 2 3 4 5

样例输出#1

6