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.

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.

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.

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.