Вам нравится играть в шахматные турниры онлайн.
В своем последнем турнире вы сыграли \(n\) игр. В этой задаче, каждая шахматная партия заканчивается либо победой, либо поражением (ничьих не бывает). Когда вы проигрываете партию, вы получаете \(0\) очков. Когда вы выигрываете, вы получаете \(1\) или \(2\) очка: если вы выиграли и предыдущую партию, вы получаете \(2\) очка, в противном случае вы получаете \(1\) очко. Если вы выиграли самую первую игру турнира, вы получаете \(1\) очко (так как не существует "предыдущей игры").
Итоги \(n\) игр записываются в строку \(s\) длиной \(n\): \(i\)-й символ \(s\) — W, если вы выиграли \(i\)-ю игру, и L, если вы проиграли \(i\)-ю игру.
После окончания турнира вы замечаете баг на сайте, который позволяет вам изменить результат не более \(k\) игр (то есть, не более \(k\) раз вы можете изменить один символ L на W, или W на L). Так как ваша единственная цель — улучшение вашего шахматного рейтинга, вы решили сжульничать и использовать данный баг.
Вычислите максимальное количество очков, которое вы можете получить с помощью жульничества оптимальным способом.
Выходные данные
Для каждого теста выведите одно целое число — максимальное количество очков, который вы можете получить, обманув оптимальным способом.
Примечание
Пояснение первого набора входных данных. Изначально ваш счет равен \(2\). Действительно, вы выиграли первую игру, за что вы получили \(1\) очко, а также выиграли третью, за что вы получили еще \(1\) очко (а не \(2\), потому что вы проиграли вторую игру).
Лучшим способом сжульничать является изменение исхода второй и четвертой игры. При этом вы выигрываете первые четыре партии (строка исходов становится WWWWL). Следовательно, ваш новый счет будет равен \(7=1+2+2+2\): \(1\) очко за первую партию и по \(2\) очка за вторую, третью и четвертую партию.
Пояснение второго набора входных данных.. Изначально ваш счет равен \(3\). Действительно, вы выиграли четвертую игру, за что вы получили \(1\) очко, а также выиграли пятую игру, так что вы получили \(2\) очка (так как вы выиграли и предыдущую игру).
Лучшим способом сжульничать является изменение исхода первой, второй, третьей и шестой игры. При этом Вы выигрываете все игры (строка исходов становится WWWWWW). Следовательно, новый счет будет равен \(11 = 1+2+2+2+2+2\): \(1\) очко за первую партию и \(2\) очка за все остальные партии.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
5 2
WLWLL
6 5
LLLWWL
7 1
LWLWLWL
15 5
WWWLLLWWWLLLWWW
40 7
LLWLWLWWWLWLLWLWWWLWLLWLLWLLLLWLLWWWLWWL
1 0
L
1 1
L
6 1
WLLWLW
|
7
11
6
26
46
0
1
6
|