Moloco là một công ty công nghệ quảng cáo giúp các doanh nghiệp trên toàn thế giới tối ưu hóa hoạt động quảng cáo trực tuyến. Công nghệ của Moloco giúp người dùng internet tiếp cận được các quảng cáo phù hợp hơn, đồng thời giúp các nhà quảng cáo đạt hiệu quả cao hơn.

Jong-seo dự đoán rằng một người dùng sẽ truy cập trang web tổng cộng $2N$ lần, và anh ấy muốn hiển thị cho người dùng hai loại quảng cáo, loại 0 và loại 1, mỗi loại $N$ lần. Vì việc liên tục hiển thị cùng một loại quảng cáo mỗi khi người dùng truy cập có thể khiến họ cảm thấy nhàm chán và làm giảm hiệu quả quảng cáo, anh ấy muốn sắp xếp hai loại quảng cáo này một cách hợp lý để tối đa hóa hiệu quả.

Để định lượng hiệu quả quảng cáo, kỹ sư Jong-seo của Moloco đã định nghĩa một chỉ số gọi là "độ nhàm chán". Với $i \leq j$, độ nhàm chán của một đoạn từ quảng cáo thứ $i$ đến thứ $j$ được định nghĩa là chênh lệch tuyệt đối giữa số lượng quảng cáo loại 0 và số lượng quảng cáo loại 1 trong đoạn đó. Độ nhàm chán mà người dùng cảm nhận cuối cùng là giá trị lớn nhất trong số độ nhàm chán của tất cả các đoạn.

Ví dụ, nếu các quảng cáo được sắp xếp theo thứ tự 00110110, độ nhàm chán của đoạn từ quảng cáo thứ $3$ đến thứ $7$ là $|1 - 4| = 3$. Vì đây là đoạn có độ nhàm chán lớn nhất, nên độ nhàm chán mà người dùng cảm nhận cuối cùng là $3$.

Thông qua các thuật toán xuất sắc của Moloco, Jong-seo đã tìm ra cách sắp xếp quảng cáo hiệu quả để tăng mức độ tương tác của người dùng. Tuy nhiên, để kiểm tra xem chỉ số "độ nhàm chán" hoạt động tốt như thế nào, anh ấy muốn giảm độ nhàm chán xuống. Vì thứ tự quảng cáo đã được xác định, để giảm độ nhàm chán, anh ấy phải tiêu tốn chi phí là $1$ cho mỗi lần hoán đổi vị trí hai quảng cáo liên tiếp. Anh ấy có thể thực hiện thao tác hoán đổi bao nhiêu lần tùy ý.

Chi phí tối thiểu cần thiết để làm cho độ nhàm chán mà người dùng cảm nhận cuối cùng nhỏ hơn hoặc bằng $K$ là bao nhiêu?

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 ($1 \le K \le N \le 500\,000$).

Dòng thứ hai chứa một chuỗi có độ dài $2N$ chỉ bao gồm các ký tự 0 và 1, đại diện cho thứ tự quảng cáo ban đầu, trong đó có $N$ ký tự 0 và $N$ ký tự 1.

Dữ liệu ra

In ra chi phí tối thiểu cần thiết để làm cho độ nhàm chán nhỏ hơn hoặc bằng $K$.

Nếu độ nhàm chán của thứ tự quảng cáo đã cho vốn đã nhỏ hơn hoặc bằng $K$, hãy in ra 0.

Có thể chứng minh rằng với mọi đầu vào hợp lệ, luôn có thể làm cho độ nhàm chán bằng $1$. Nói cách khác, đáp án luôn tồn tại.

Ví dụ

Dữ liệu vào 1

4 2
00110110

Dữ liệu ra 1

1

Dữ liệu vào 2

4 2
11110000

Dữ liệu ra 2

3

Dữ liệu vào 3

4 1
10011001

Dữ liệu ra 3

2