CF248D.Sweets for Everyone!

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.

因为他深知，住在下方呼呜镇（Whoville）的每一位呼呜人（Who），
此刻正忙着悬挂槲寄生花环。
“他们还在挂长筒袜呢！”他轻蔑地咆哮道，
“明天就是圣诞节了！它几乎就要到了！”

——苏斯博士（Dr. Seuss），《格林奇偷走圣诞节》（How The Grinch Stole Christmas）

圣诞节庆祝活动即将来到呼呜镇。辛迪·露·呼呜（Cindy Lou Who）与她的父母——卢·露·呼呜（Lou Lou Who）和贝蒂·露·呼呜（Betty Lou Who）决定向他们所在街道上的所有人赠送糖果。他们决定向街道上每户人家各赠送一千克糖果。因此，他们所需糖果的总千克数，恰好等于该街道上的房屋总数。

卢·呼呜一家所居住的这条街道，可被建模为 $n$ 个长度相等、首尾相连的连续路段。从任一路段出发，可在单位时间内移动至其相邻路段。每一路段属于以下三种类型之一：空地、房屋或商店。辛迪·露·呼呜一家可在商店中购买糖果，但每家商店最多只能购买一千克糖果（店主们很关心呼呜镇居民，不希望他们因过量食用糖果而吃坏肚子）。

卢·呼呜一家离开自家后，将出现在道路的第一路段。抵达该第一路段同样需要消耗一个单位时间。我们可假设辛迪与她的父母能携带无限数量的千克级糖果。每当他们位于某房屋路段时，他们可选择向该房屋居民赠送一千克糖果，也可直接移至另一路段；若已向某房屋居民赠送过糖果，则不可重复赠送。类似地，当他们位于某商店路段时，可选择在其中购买一千克糖果，或跳过该商店；若已在某商店购买过一千克糖果，则该店主会记住他们，之后无论他们再次光临多少次，都不会再售出哪怕一颗糖果。购买及赠送糖果本身所耗时间可忽略不计。卢·呼呜一家不希望任何一户人家得不到糖果。

卢·呼呜一家希望整个送糖过程耗时不超过 $t$ 个时间单位，因为他们迫切需要留出充足时间来筹备圣诞节庆典。为了确保有足够时间完成全部送糖任务，他们可能需要预先额外携带 $k$ 千克糖果。

辛迪·露·呼呜想知道：他们至少需随身携带多少千克（即最小的 $k$ 值）糖果，才能保证在时限内向街道上每一户人家都成功赠送糖果？

你的任务是编写一个程序，计算出满足条件的最小可能的 $k$ 值。

The first line of the input contains two space-separated integers n and t (2 ≤ n ≤ 5·105, 1 ≤ t ≤ 109). 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.

输入的第一行包含两个以空格分隔的整数 $n$ 和 $t$（$2 \leq n \leq 5\cdot10^5$，$1 \leq t \leq 10^9$）。
输入的第二行包含 $n$ 个字符，其中第 $i$ 个字符为：

• "H"（表示第 $i$ 个路段上有一座房屋），
• "S"（表示第 $i$ 个路段上有一家商店），或
• "."（表示第 $i$ 个路段上既无房屋也无商店）。

保证至少存在一个包含房屋的路段。

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.

如果不存在一个单一的 $k$ 值，使得能在至多 $t$ 单位时间内将糖果分发给所有人，则在一行中输出 -1（不带引号）。否则，在一行中输出最小的可能的 $k$ 值。

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.

在第一个例子中，商店的数量与房屋的数量相等。如果这家人不从家中携带任何糖果（即携带 0 千克），那么为了招待第一栋房屋的居民，他们至少需要向后走一步，而他们完全没有时间这样做；但如果他们从家中携带 1 千克糖果，则无需返回。

在第二个例子中，商店的数量等于房屋的数量，且时间充裕。他们可以沿一个方向依次经过所有商店领取糖果，并在沿相反方向经过时分发糖果。

在第三个例子中，街道上的商店数量少于房屋数量。卢·胡一家必须从家中携带所缺数量的糖果（单位：千克）。