题目内容

你管理一条狭长的农田，划分为 $n$ 个连续的区块，编号 $1$ 到 $n$。每个区块的土壤状态用一个整数表示：$0$ 表示湿度正常，$1$ 表示干旱。你需要从区块 $1$ 依次走到区块 $n$，并保证途中遇到的每一块干旱区块都得到及时浇灌。

你带有一台移动式喷灌机，整个行程中最多可以启动 $m$ 次。每次启动时，喷灌机会从你所在的区块开始，向后连续 $x$ 个区块（包含当前区块）均匀洒水，使这些区块变为湿润状态。你需要选择一个固定的喷灌范围长度 $x$，使得你可以在不超过 $m$ 次启动的限制下，顺利地处理所有干旱区块。一旦你经过某一区块，发现它依然干旱，就必须立即启动一次喷灌（即便这会导致次数用尽）。

请你求出在满足要求的前提下，喷灌范围长度 $x$ 的最小值。若初始所有区块均已湿润，则 $x$ 可以为 $0$。

数据范围：

• 测试数据组数 $T$ 满足 $1 \le T \le 10^3$。
• 每组数据中，区块数量 $n$ 满足 $1 \le n \le 2 \times 10^5$，最大启动次数 $m$ 满足 $1 \le m \le n$。
• 所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。
• 每个状态值仅为 0 或 1。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。随后每组数据：

• 第一行包含两个整数 $n$ 和 $m$，分别表示区块数量与最大启动次数。
• 第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$，其中 $s_i \in \{0, 1\}$，表示第 $i$ 个区块的土壤状态。

输出描述

对于每组测试数据，输出一行一个整数，表示满足条件的最小喷灌范围长度 $x$。

样例1

输入

1
1 1
1

输出

1

说明

只有 1 个区块，且该区块干旱（$s_1 = 1$）。你必须启动 1 次喷灌。喷灌范围长度 $x$ 最小为 1 即可覆盖该区块，因此答案为 1。

样例2

输入

1
5 2
1 0 0 1 0

输出

1

说明

区块序列：1（干旱），0，0，1（干旱），0。最多可启动 $m = 2$ 次。当 $x = 1$ 时，在第 1 个区块启动一次，覆盖该区块；走到第 4 个区块时启动第二次，覆盖该区块。两次即可处理所有干旱区块，因此 $x = 1$ 可行。更小的 $x$ 不存在，故答案为 1。

样例3

输入

1
6 1
0 1 1 0 1 0

输出

4

说明

区块序列：0，1（干旱），1（干旱），0，1（干旱），0。最多只能启动 $m = 1$ 次。走到第 2 个区块时遇到干旱，必须启动喷灌，这一次必须覆盖后面所有干旱区块。干旱区块位置为 2、3、5。从 2 开始，需要 $x$ 满足 $2 + x - 1 \ge 5$，即 $x \ge 4$。当 $x = 4$ 时，覆盖区块 2 到 5，一次启动即可。因此最小 $x$ 为 4。

样例4

输入

1
3 2
0 0 0

输出

0

说明

所有 3 个区块初始均为湿润状态（$s_i = 0$），不存在干旱区块。根据题意，此时喷灌范围长度 $x$ 可以为 0。因此输出 0。