Siêu đô thị bò Bovinopolis đang phân chia lại các khu vực bầu cử! Đây luôn là một quá trình chính trị gây tranh cãi giữa hai giống bò lớn (Holstein và Guernsey) sinh sống tại đó, bởi cả hai giống đều muốn bảo đảm mình duy trì đủ ảnh hưởng trong chính quyền Bovinopolis.

Vùng đô thị Bovinopolis mở rộng gồm một dãy \(N\) đồng cỏ (\(1 \leq N \leq 3 \cdot 10^5\)), mỗi đồng cỏ có đúng một con bò thuộc giống Holstein hoặc Guernsey.

Chính quyền Bovinopolis muốn chia vùng đô thị mở rộng thành một số khu vực liên tiếp sao cho mỗi khu vực chứa không quá \(K\) đồng cỏ (\(1 \leq K \leq N\)), và mỗi đồng cỏ thuộc đúng một khu vực. Vì chính quyền hiện do giống Holstein kiểm soát, họ muốn tìm một cách phân chia lại sao cho số khu vực có đa số Guernsey hoặc có kết quả hòa là nhỏ nhất (một khu vực hòa nếu số bò Guernsey bằng số bò Holstein).

Một liên minh những con bò Guernsey đang lo ngại muốn tìm hiểu mức thiệt hại mà việc phân chia lại của chính quyền có thể gây ra. Hãy giúp họ xác định, trong trường hợp xấu nhất, số khu vực tối thiểu có đa số Guernsey hoặc có kết quả hòa.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) cách nhau bởi dấu cách. Dòng thứ hai chứa một xâu có độ dài \(N\). Mỗi ký tự là H hoặc G, tương ứng với Holstein hoặc Guernsey.

Dữ liệu ra

In ra số khu vực có đa số Guernsey hoặc có kết quả hòa nhỏ nhất có thể.

Ví dụ

7 2
HGHGGHG

3

Nguồn

Đề bài gốc: USACO 2019 January Contest, Platinum — Redistricting

Tác giả: Dhruv Rohatgi