CF2245A.Who Watches the Watchpig?

There are $n$ piggies standing in a line, numbered from $1$ to $n$ from left to right. Each piggy is either facing left or right.

Two piggies $x$ and $y$ are called a watchpig pair if $x \lt y$, $x$ is facing right, and $y$ is facing left.

You are given an integer $k$ such that $1 \le k \lt n$. A piggy is called safe if it belongs to at least $k$ watchpig pairs.

Your task is to make all piggies safe. To achieve this, you can choose any number of piggies and flip their directions (changing left to right or vice versa).

Compute the minimum number of piggies you need to turn around so that every piggy becomes safe, or report that it is impossible to do so.

有 $n$ 只小猪排成一列，从左到右依次编号为 $1$ 到 $n$。每只小猪面朝左或右。

若满足 $x \lt y$、$x$ 面朝右、且 $y$ 面朝左，则称小猪 $x$ 和 $y$ 构成一对“守望对”（watchpig pair）。

给定整数 $k$，满足 $1 \le k \lt n$。若一只小猪至少属于 $k$ 个守望对，则称其为“安全的”。

你的任务是使所有小猪都变为安全的。为此，你可以任选若干只小猪并翻转其朝向（即左变右、右变左）。

请计算使所有小猪均安全所需的最少翻转次数；若不可能实现，请报告该情况。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \lt n \le 100$), representing the number of piggies and the number of watchpig pairs a piggy needs to belong to, respectively.

The second line contains a string $s$ of length $n$ consisting only of the characters $\mathtt{L}$ and $\mathtt{R}$. For every $1 \le i \le n$, if $s_i= \mathtt{L}$, piggy $i$ is facing left; otherwise, if $s_i= \mathtt{R}$, piggy $i$ is facing right.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \lt n \le 100$），分别表示小猪的数量以及一只小猪需要所属的“守望对”（watchpig pair）的数量。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，其仅由字符 $\mathtt{L}$ 和 $\mathtt{R}$ 组成。对于每个 $1 \le i \le n$，若 $s_i = \mathtt{L}$，则第 $i$ 只小猪面朝左；否则（即 $s_i = \mathtt{R}$），则第 $i$ 只小猪面朝右。

For each test case, if it is impossible to make every piggy safe, output $-1$. Otherwise, output the minimum number of piggies you need to turn around so that every piggy becomes safe.

对于每个测试用例，如果无法使所有存钱罐变得安全，则输出 $-1$；否则，输出需要翻转的存钱罐的最小数量，使得所有存钱罐均变得安全。

In the first test case, one optimal solution is to turn piggy $1$ around. Both piggy $1$ and piggy $3$ now belong to the watchpig pair $(1,3)$, and piggy $2$ belongs to the watchpig pair $(1,2)$. Every piggy belongs to at least $k=1$ watchpig pairs, hence every piggy is safe.

In the second test case, it can be proven that it is impossible to make every piggy safe.

In the third test case, one optimal solution is to turn piggies $2$ and $5$ around. For example, piggy $2$ is now safe, as it belongs to both $(2,3)$ and $(2,5)$. Piggy $4$ is also safe, as it belongs to both $(4,5)$ and $(4,6)$. The rest of the piggies are all safe.

在第一个测试用例中，一种最优解是将小猪 $1$ 翻转。此时，小猪 $1$ 和小猪 $3$ 均属于守卫对 $(1,3)$，而小猪 $2$ 属于守卫对 $(1,2)$。每只小猪至少属于 $k=1$ 个守卫对，因此每只小猪都是安全的。

在第二个测试用例中，可以证明：不可能使所有小猪都变得安全。

在第三个测试用例中，一种最优解是将小猪 $2$ 和小猪 $5$ 翻转。例如，小猪 $2$ 现在是安全的，因为它同时属于 $(2,3)$ 和 $(2,5)$；小猪 $4$ 也是安全的，因为它同时属于 $(4,5)$ 和 $(4,6)$；其余的小猪也全部安全。