2070C.md (2678B)
1 Source: https://codeforces.com/problemset/problem/2070/C 2 3 C. Limited Repainting 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a strip, consisting of $n$ cells, all cells are initially colored red. 22 23 In one operation, you can choose a segment of consecutive cells and paint them blue. Before painting, the chosen cells can be either red or blue. Note that it is not possible to paint them red. You are allowed to perform at most $k$ operations (possibly zero). 24 25 For each cell, the desired color after all operations is specified: red or blue. 26 27 It is clear that it is not always possible to satisfy all requirements within $k$ operations. Therefore, for each cell, a penalty is also specified, which is applied if the cell ends up the wrong color after all operations. For the $i$-th cell, the penalty is equal to $a_i$. 28 29 The penalty of the final painting is calculated as the maximum penalty among all cells that are painted the wrong color. If there are no such cells, the painting penalty is equal to $0$. 30 31 What is the minimum penalty of the final painting that can be achieved? 32 33 Input 34 35 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 36 37 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 3 \cdot 10^5$; $0 \le k \le n$) — the length of the strip and the maximum number of operations. 38 39 The second line contains a string $s$, consisting of $n$ characters 'R' and/or 'B'. 'R' means that the cell should be painted red. 'B' means that the cell should be painted blue. 40 41 The third line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the penalty for each cell. 42 43 The sum of $n$ over all test cases does not exceed $3 \cdot 10^5$. 44 45 Output 46 47 For each test case, print a single integer — the minimum penalty of the final painting. 48 49 Example 50 51 Input 52 53 ``` 54 5 55 56 4 1 57 58 BRBR 59 60 9 3 5 4 61 62 4 1 63 64 BRBR 65 66 9 5 3 4 67 68 4 2 69 70 BRBR 71 72 9 3 5 4 73 74 10 2 75 76 BRBRBBRRBR 77 78 5 1 2 4 5 3 6 1 5 4 79 80 5 5 81 82 RRRRR 83 84 5 3 1 2 4 85 ``` 86 87 Output 88 89 ``` 90 3 91 3 92 0 93 4 94 0 95 ``` 96 97 Note 98 99 In the first test case, you can paint the cells from $1$ to $3$. The painting will be BBBR. So, only cell $2$ is painted the wrong color. Therefore, the penalty for it is the final penalty and equals $3$. 100 101 In the second test case, the painting BBBR will now result in a penalty of $5$. However, if you paint the cells from $1$ to $1$, resulting in BRRR, then only cell $3$ is painted the wrong color. The final penalty is $3$. 102 103 In the third test case, you can paint the cells from $1$ to $1$ and from $3$ to $3$. Then all cells will be the correct color, the penalty equals $0$.