CF2042C.Competitive Fishing

Alice 和 Bob 参加了一个钓鱼比赛，他们一共钓到了 $n$ 条鱼，鱼的大小从 $1$ 到 $n$ 升序排序。

两人的总分计算如下：首先，选择一个整数 $m$，所有鱼都被依次分到 $m$ 个非空连续区间，一条鱼只能被分到一个区间，并且区间从小到大排列。比如：第二个区间的鱼必须全部大于第一个区间的鱼。

接着，每条鱼都按照区间编号被分配了分数，第 $1$ 个区间的鱼分数全部为 $0$，第 $2$ 个区间鱼的分数全部为 $1$……第 $i$ 个区间鱼的分数全部为 $(i-1)$。

两人的分数即为他们各自钓到鱼的分数之和。

你想要让 Bob 的分数比 Alice 高至少 $k$ 分。求划分的区间个数 $m$ 的最小值。

第一行，一个整数 $t$ ($1\le t \le 10^4$)，表示数据组数。

对于每组数据：

第一行，两个整数 $n,k$ ($1\le n\le 2\times 10^5$；$1\le k\le 10^9$)。

第二行，一个长度为 $n$ 的 0-1 字符串，第 $i$ 个位置为 $0$，代表第 $i$ 条鱼属于 Alice。第 $i$ 个位置为 $1$，代表第 $i$ 条鱼属于 Bob。

对于每组数据，输出一行，一个整数，表示将鱼分成组数的最小值。如果无解，输出 -1。

翻译：HYdroKomide

null