圣诞节庆祝活动即将在 Whoville 举行。 Cindy Lou Who 和她的父母 Lou Lou Who 和 Betty Lou Who 决定向街上的所有人赠送糖果。他们决定给街上每户人家赠送一公斤糖果。因此,他们需要的糖果数量与街道上的房屋数量一样多。
Lou Who一家居住的街道可以表示为n个连续的等长路段。您可以在一个单位时间内从任何一个部分转到相邻的一个部分。每个部分都是三种类型之一:一块空地、一栋房子或一家商店。 Cindy Lou 和她的家人可以在一家商店购买糖果,但一间商店最多只能购买一公斤糖果(商贩关心 Whoville 的居民不要吃太多糖果)。
楼何一家离开家后,他们将走到第一段路。想要走到这段路,他们也需要一个单位的时间。我们可以假设辛迪和她的爸爸妈妈可以携带无限数量的糖果。每当他们到达某个房屋区域时,他们就可以向房屋内的居民赠送一公斤糖果,或者他们可以简单地移动到另一个区域。如果家人已经给房子里的居民送过糖果,他们就不能再这样做了。同样,如果他们在商店区,他们可以在其中购买一公斤糖果,也可以跳过这家商店。如果他们在商店买了一公斤糖果,商店的卖家就会记住他们,如果他们再来,他们不会再卖给他们一颗糖果。买糖果和送糖果的时间可以忽略不计。卢氏族不希望任何家族的人没有食物。
Lou Whos希望花不超过t个时间单位的时间来分发糖果,因为他们真的希望有足够的时间来准备圣诞节庆祝活动。为了有时间提供所有糖果,他们可能必须首先携带额外的 k 公斤糖果。
Cindy Lou 想知道他们需要携带的最少 k 公斤糖果,以便有时间向街道上每所房子的居民分发糖果。
您的任务是编写一个程序来确定 k 的最小可能值。
输入
输入的第一行包含两个空格分隔的整数 n 和 t (2 ≤ n ≤ 5·105, 1 ≤ t ≤ 109)。输入的第二行包含 n 个字符,其中第 i 个字符等于“H”(如果第 i 个段包含房屋)、“S”(如果第 i 个段包含商店)或“.”。 (如果第 i 个段不包含房屋或商店)。
保证至少有一个段有房子。
输出
如果没有单一的 k 值可以在最多 t 个时间单位内向每个人提供糖果,则在单行中打印“-1”(不带引号)。否则,在一行上打印 k 的最小可能值。
示例
输入 #1
6 6 HSHSHS
输出 #1
1
输入 #2
14 100 ...HHHSSS...SH
输出 #2
0
输入 #3
23 50 HHSS.......SSHHHHHHHHHH
输出 #3
8
注意
在第一个示例中,商店与房屋一样多。如果一家人不从家里带一公斤糖果,为了招待第一间房子的居民,他们至少需要退一步,而且根本没有时间这样做。如果他们拿走一公斤糖果,他们就不需要回去了。
在第二个例子中,商店的数量等于房屋的数量和充足的时间。所有商店均可向一个方向分发糖果,并在经过相反方向时给予糖果。
在第三个例子中,街上的商店比房屋少。卢一家不得不从家里带走失踪的几公斤糖果。