Lắp đặt wifi

Quân là người quản lí của kí túc xá trường chuyên Lê Quý Đôn. Kí túc xá chỉ có một tầng và có \(n\) phòng, các phòng được xây liên tiếp nhau trên một đường thẳng, các phòng được đánh số từ \(1\) đến \(n\).

Mỗi khi bắt đầu năm học, Quân lại phụ trách công việc lắp đặt wifi cho học sinh. Và Quân phải đảm bảo rằng, \(n\) phòng của học sinh đều bắt được wifi. Một số phòng có đã sẵn chỗ để đặt router mạng. Quân không thể đặt router mạng ở những phòng không có sẵn chỗ để đặt. Khi Quân đặt router ở phòng thứ \(i\), thì toàn bộ những phòng từ \(max(1, i - k)\) đến \(min(n, i + k)\) đều có thể bắt wifi tại phòng \(i\), \(k\) là độ phủ sóng của router. Với tất cả mọi phòng thì giá trị \(k\) không thay đổi.

Tuy nhiên, khi chỉ lắp đặt router ở những nơi có sẵn chố để đặt router, có thể một số phòng sẽ không bắt được wifi. Ví dụ nếu phòng \(4\) và phòng \(10\) có router, mỗi router có độ phủ sóng là \(2\), thì phòng \(7\) sẽ không bắt được wifi bởi vì router ở hai phòng kia đều không phủ tới được phòng \(7\). Vì vậy, Quân quyết định mua thêm dây mạng để kết nối trực tiếp tới wifi phòng của Quân (phòng này đảm bảo luôn luôn có wifi, và phòng này không nằm trong khuôn viên của kí túc xá nhà trường) . Chi phí mua dây mạng kết nối trực tiếp từ phòng \(i\) đến phòng \(Quân\) là \(i\) triệu đồng. Chi phí để lắp đặt router ở phòng kí túc xá thứ \(i\) là \(i\) triệu đồng.

Vì số phòng kí túc xá rất lớn (có thể lên tới 200000 phòng), nếu tính toán không hợp lí thì số tiền phải bỏ ra để mua dây kết nối và lắp đặt router có thể là rất lớn. Biết Quân từng là học sinh lớp chuyên tin, nhà trường giao cho Quân một bài toán cực khó: tính số tiền nhỏ nhất để đặt router mạng sao cho \(n\) phòng kí túc xá đều có thể bắt được wifi. Tuy nhiên, trí tuệ con người là có hạn, Quân chỉ có thể tính toán nếu kí túc xá chỉ có \(2\) - \(5\) phòng, Quân biết rằng, cách duy nhất để có thể giải bài toán này chính là viết code. Nhưng hơn \(30\) năm rồi Quân chưa đụng tới Codeblocks, kĩ năng code cũng như tư duy suy nghĩ cũng phai nhạt dần, Quân đành phải nhờ các bạn giải giúp bài toán này vậy.

Input

Dòng đầu tiên là hai số nguyên dương \(n, k\) - số lượng phòng và độ phủ sóng router. \((n, k <= 2.10^5)\).

Dòng thứ 2 gồm một xâu kí tự độ dài \(n\), chỉ chứa kí tự \(0\) và \(1\). Các kí tự được đánh số từ \(1\) đến \(n\). Kí tự \(i\) nếu là \(0\) thì phòng thứ \(i\) không có sẵn chỗ để đặt router mạng, với \(1\) thì ngược lại.

Output

Một dòng duy nhất chứa kết quả bài toán.

Example

5 2
00100

3

6 1
000000

21

4 1
0011

4

5 1
01010

6

10 1
0011100011

25

Scoring

\(30\%\) số test có \(n <= 20\).

\(30\%\) số test có \(n <= 1000\).

\(40\%\) còn lại không có ràng buộc gì thêm.