以下题面由 AI 翻译。

题目描述

给定一个包含 n 个元素的整数序列（编号从 1 到 n），你的任务是找到最小值 M，使得我们可以找到 k + 1 个整数 0 = p(0) < p(1) < p(2) < ... < p(k-1) < p(k) = n，使得对于任意 i 从 0 到 k - 1，位置 p(i)+1 到位置 p(i+1) 的元素之和不超过 M。

输入格式

输入文件包含多个测试用例。每个测试用例的第一行是测试用例的数量 nTest（1 ≤ nTest ≤ 10）。每个测试用例的结构如下：

• 第一行包含两个整数 n 和 k（1 ≤ k ≤ n ≤ 15000）。
• 接下来的 n 行每行包含一个整数，表示序列中的元素。

输出格式

对于每个测试用例，输出一行，表示最小值 M。

示例

输入：

1
9 4
1
1
1
3
2
2
1
3
1

输出：

5

提示

• 约束条件和提示部分可能不存在，或者合并为一个部分。
• 如果存在输入/输出示例，请保留它们不变，并保留所有标记。
• 建议使用字面翻译，但如果提供的是 HTML 文件，则可以将其转换为 Markdown 格式。