Minimum Maximum Weight Partitioning

Ringo needs to break the curse of the Princess Frog by solving a challenge created by Tabuki.

A binary string (a string of 0s and 1s) of length \(n\) is given. The weight of a 01 string is defined as the product of the number of 0s and the number of 1s in that string.

You are given a binary string of length \(n\) and an integer \(k\). You need to divide the entire string into exactly \(k\) contiguous substrings. For a given division, let the weight of a substring be defined as above and let \(W\) be the maximum weight among these \(k\) substrings. Your task is to minimize \(W\); that is, find the minimum possible value of the maximum weight among the \(k\) substrings.

The formula for the weight of a binary string \(s\) is given in \(\LaTeX\) as: \(\text{weight}(s) = (\# \text{ of } 0) \times (\# \text{ of } 1)\).

inputFormat

The first line contains two integers \(n\) and \(k\) separated by a space, where \(n\) is the length of the binary string and \(k\) is the number of segments to divide the string into.

The second line contains a binary string of length \(n\) consisting only of characters '0' and '1'.

outputFormat

Output a single integer, the minimum possible value of the maximum weight among these \(k\) segments.

sample

5 3
01010

1