D. Конфеты - каждому!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout
Скоро Новый год. Мы все вместе в Простоквашино уедем. Будем там на лыжах кататься, печку топить, а в Новый год карнавал устроим. Ты нарядишься казаком или узбеком. Будешь вкусный плов готовить и казачью песню петь про ракитовый куст.
Эдуард Николаевич Успенский

В деревне Простоквашино празднуют Новый год. Дядя Федор вместе со своими друзьями — котом Матроскиным и псом Шариком решил угостить всех жителей на своей улице конфетами. Дядя Федор и его друзья решили, что жителям каждого дома на их улице они подарят по одному килограмму конфет. Таким образом им потребуется столько килограммов конфет, сколько домов есть на их улице.

Улицу, где живут трое из Простоквашино, можно мысленно разбить на n последовательных участков одинаковой длины. С любого участка можно перейти на один из соседних участков за одну единицу времени. Каждый из участков бывает одного из трех типов: пустой участок, участок с домом или участок с магазином. В магазине Дядя Федор и его друзья могут купить конфеты, но не более одного килограмма конфет в одном магазине (продавцы заботятся о том, чтобы жители деревни не злоупотребляли сладким).

После того, как трое из Простоквашино выйдут из своего дома, они окажутся на первом участке дороги. Для попадания на этот участок дороги тоже требуется одна единица времени. Можно считать, что Дядя Федор и его друзья могут нести неограниченное число килограммов конфет. Каждый раз, когда они оказываются на участке с домом, они могут отдать один килограмм конфет жителям дома, а могут просто перейти на другой участок. Если трое из Простоквашино уже отдавали конфеты жителям какого-то дома, то еще раз они этого сделать не могут. Аналогично, если Дядя Федор и его друзья находятся на участке с магазином, то они могут либо купить в нем килограмм конфет, либо пропустить этот магазин. Если в каком-то магазине они уже купили килограмм конфет, то продавец их запомнил и второй раз не продаст им больше ни грамма конфет. Временем на покупку и вручение конфет можно пренебречь. Дядя Федор с котом Матроскиным и псом Шариком не хотят, чтобы жители хотя бы одного дома остались без угощения.

Трое из Простоквашино хотят потратить не более t единиц времени на раздачу конфет, чтобы успеть подготовиться к празднованию Нового года. Для того, чтобы успеть раздать все конфеты, возможно, придется изначально взять с собой дополнительно k килограммов конфет.

Дядя Федор хочет знать минимальное число k килограммов конфет, которое необходимо взять с собой, чтобы успеть угостить жителей каждого дома на своей улице сладостями.

Ваша задача — написать программу, которая определит минимально возможное значение k.

Входные данные

Первая строка входных данных содержит два целых числа n и t, разделенных пробелами (2 ≤ n ≤ 5·105, 1 ≤ t ≤ 109). Вторая строка входных данных содержит n символов, i-ый из которых равен «H» (если i-ый участок содержит дом), «S» (если i-ый участок содержит магазин) или «.» (если i-ый участок не содержит ни дома, ни магазина).

Гарантируется, что имеется хотя бы один участок с домом.

Выходные данные

Если не существует ни одного значения k, при котором возможно не более, чем за t единиц времени угостить обитателей всех домов, то в единственной строке выведите «-1» (без кавычек). Иначе в единственной строке выведите минимально возможное значение k.

Примеры
Входные данные
6 6
HSHSHS
Выходные данные
1
Входные данные
14 100
...HHHSSS...SH
Выходные данные
0
Входные данные
23 50
HHSS.......SSHHHHHHHHHH
Выходные данные
8
Примечание

В первом примере магазинов столько же, сколько и домов. Если не брать с собой ни одного килограмма конфет, то для того, чтобы угостить жителей самого первого дома потребуется сделать хотя бы один шаг назад, на что у друзей из Простоквашино абсолютно нет времени. Если же взять с собой один килограмм конфет, то возвращаться ни разу не потребуется.

Во втором примере число магазинов равняется числу домов и времени предостаточно. Можно купить во всех магазинах конфеты пройдя улицу в одном направлении и раздать их при проходе в обратном направлении.

В третьем примере на улице меньше магазинов, чем домов. Придется друзьями из Простоквашино взять недостающее число килограммов конфет с собой из дома.