该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

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

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

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

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

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

Format

Input

第一行一个正整数 $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$。

Output

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

Samples

3
5 3
2 4 7 3 5
4 2
1 2 3 4
3 3
10 1 8

8
6
10

Limitation

1s, 1024KiB for each test case.