Sweets for Everyone!

题意翻译

圣诞节到了！你现在想去给每家每户分糖果。‘H’表示这里有一户人家，‘S’表示这里有一家超市，‘.’表示这里为空地，当你经过超市时，可以买1kg糖果（如果之前来买过，则当空地看）。现在有n个地方，因为要筹备圣诞节，你只有t的时间来完成这些任务，问能否让每户人家都分到1kg糖果。因为时间原因，你需要提前准备一些糖果，如果可以完成上述要求，输出最少需要提前准备多少个糖果，如果不行则输出-1.

题目描述

For he knew every Who down in Whoville beneath, Was busy now, hanging a mistletoe wreath. "And they're hanging their stockings!" he snarled with a sneer, "Tomorrow is Christmas! It's practically here!" Dr. Suess, How The Grinch Stole Christmas Christmas celebrations are coming to Whoville. Cindy Lou Who and her parents Lou Lou Who and Betty Lou Who decided to give sweets to all people in their street. They decided to give the residents of each house on the street, one kilogram of sweets. So they need as many kilos of sweets as there are homes on their street. The street, where the Lou Who family lives can be represented as $ n $ consecutive sections of equal length. You can go from any section to a neighbouring one in one unit of time. Each of the sections is one of three types: an empty piece of land, a house or a shop. Cindy Lou and her family can buy sweets in a shop, but no more than one kilogram of sweets in one shop (the vendors care about the residents of Whoville not to overeat on sweets). After the Lou Who family leave their home, they will be on the first section of the road. To get to this section of the road, they also require one unit of time. We can assume that Cindy and her mom and dad can carry an unlimited number of kilograms of sweets. Every time they are on a house section, they can give a kilogram of sweets to the inhabitants of the house, or they can simply move to another section. If the family have already given sweets to the residents of a house, they can't do it again. Similarly, if they are on the shop section, they can either buy a kilo of sweets in it or skip this shop. If they've bought a kilo of sweets in a shop, the seller of the shop remembered them and the won't sell them a single candy if they come again. The time to buy and give sweets can be neglected. The Lou Whos do not want the people of any house to remain without food. The Lou Whos want to spend no more than $ t $ time units of time to give out sweets, as they really want to have enough time to prepare for the Christmas celebration. In order to have time to give all the sweets, they may have to initially bring additional $ k $ kilos of sweets. Cindy Lou wants to know the minimum number of $ k $ kilos of sweets they need to take with them, to have time to give sweets to the residents of each house in their street. Your task is to write a program that will determine the minimum possible value of $ k $ .

输入输出格式

输入格式

The first line of the input contains two space-separated integers $ n $ and $ t $ ( $ 2<=n<=5·10^{5},1<=t<=10^{9} $ ). The second line of the input contains $ n $ characters, the $ i $ -th of them equals "H" (if the $ i $ -th segment contains a house), "S" (if the $ i $ -th segment contains a shop) or "." (if the $ i $ -th segment doesn't contain a house or a shop). It is guaranteed that there is at least one segment with a house.

输出格式

If there isn't a single value of $ k $ that makes it possible to give sweets to everybody in at most $ t $ units of time, print in a single line "-1" (without the quotes). Otherwise, print on a single line the minimum possible value of $ k $ .

输入输出样例

输入样例 #1

6 6
HSHSHS

输出样例 #1

1

输入样例 #2

14 100
...HHHSSS...SH

输出样例 #2

0

输入样例 #3

23 50
HHSS.......SSHHHHHHHHHH

输出样例 #3

8

说明

In the first example, there are as many stores, as houses. If the family do not take a single kilo of sweets from home, in order to treat the inhabitants of the first house, they will need to make at least one step back, and they have absolutely no time for it. If they take one kilogram of sweets, they won't need to go back. In the second example, the number of shops is equal to the number of houses and plenty of time. Available at all stores passing out candy in one direction and give them when passing in the opposite direction. In the third example, the shops on the street are fewer than houses. The Lou Whos have to take the missing number of kilograms of sweets with them from home.

题意翻译

圣诞节到了！你现在想去给每家每户分糖果。‘H’表示这里有一户人家，‘S’表示这里有一家超市，‘.’表示这里为空地，当你经过超市时，可以买1kg糖果（如果之前来买过，则当空地看）。现在有n个地方，因为要筹备圣诞节，你只有t的时间来完成这些任务，问能否让每户人家都分到1kg糖果。因为时间原因，你需要提前准备一些糖果，如果可以完成上述要求，输出最少需要提前准备多少个糖果，如果不行则输出-1.