Ăn kẹo trên phố

Một con phố được chia thành $n$ đoạn liên tiếp có độ dài bằng nhau, đánh số từ $1$ đến $n$. Mỗi đoạn thuộc một trong ba loại:

• Nhà (ký hiệu "H"): có người ở, cần được phát đúng $1$ kg kẹo.
• Cửa hàng (ký hiệu "S"): có thể mua kẹo, nhưng mỗi cửa hàng chỉ bán tối đa $1$ kg.
• Đất trống (ký hiệu "."): không có gì.

Một gia đình xuất phát từ nhà của họ. Để đi tới đoạn thứ $1$ của con phố họ mất $1$ đơn vị thời gian. Sau đó, mỗi lần di chuyển sang một đoạn kề (sang trái hoặc sang phải) mất $1$ đơn vị thời gian. Họ có thể mang theo số lượng kẹo không giới hạn.

Khi đang đứng ở một đoạn là nhà, họ có thể phát $1$ kg kẹo cho nhà đó (mỗi nhà chỉ nhận một lần). Khi đang đứng ở một đoạn là cửa hàng, họ có thể mua $1$ kg kẹo ở đó (mỗi cửa hàng chỉ mua được một lần). Thời gian để mua và phát kẹo được bỏ qua.

Gia đình muốn phát kẹo cho tất cả các nhà và chỉ được dùng không quá $t$ đơn vị thời gian. Vì trên phố có thể không đủ cửa hàng, họ có thể mang sẵn thêm $k$ kg kẹo từ nhà đi.

Hãy tìm giá trị nhỏ nhất của $k$ để có thể phát kẹo cho mọi nhà trong thời gian không quá $t$. Nếu không tồn tại giá trị $k$ nào thỏa mãn, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $t$.
• Dòng thứ hai chứa xâu gồm $n$ ký tự, ký tự thứ $i$ là "H", "S" hoặc "." mô tả loại của đoạn thứ $i$.

Dữ liệu bảo đảm có ít nhất một đoạn là nhà.

Dữ liệu ra

In ra một số nguyên là giá trị nhỏ nhất của $k$, hoặc $-1$ nếu không thể.

Ràng buộc

• $2\le n\le 5·{10}^5$
• $1\le t\le {10}^9$

Ví dụ