On his tour across America, IShowSpeed (aka Darren Watkins Jr.) makes a stop at the legendary Terry Black's Barbecue, a staple of Austin.
The restaurant has $$$n$$$ $$$(1 \le n \le 10^5)$$$ tables arranged in a row, each with either a beef rib on top of it or not. More formally, let $$$s$$$ be a binary string of length $$$n$$$, where $$$s_i = 1$$$ if table $$$i$$$ has a beef rib, and $$$s_i = 0$$$ if table $$$i$$$ does not have a beef rib.
Speed is allowed to make exactly $$$2$$$ runs through the dining area. On each run, he chooses a contiguous range of exactly $$$k$$$ $$$(1 \le k \le n \le 10^5)$$$ tables and eats every rib on those tables. After a run, all ribs on the chosen tables have been eaten, so those tables contain no ribs for any future run. The two ranges are allowed to overlap, but a rib can only be eaten once, so any table included in both ranges contributes at most one rib to Speed's total.
Speed is very hungry after doing backflips and traveling around Austin all day, so he wants to maximize the number of beef ribs he eats. Help Speed figure out the maximum amount of beef ribs he can eat if he chooses where to make his runs optimally.
The first line contains integers $$$n, k$$$ $$$(1 \le k \le n \le 10^5)$$$, the total number of tables and the number of tables Speed goes through in a run respectively.
The second line contains $$$s$$$, a binary string of length $$$n$$$, representing which tables contain dino ribs
Output a single number, the total number of ribs Speed can eat if he chooses where to make his runs optimally.
11 301110100110
5
In the first test case, the answer is 5 as you can choose the two runs of size 3 ($$$k = 3$$$) as follows (the brackets here encapsulate where the runs are chosen)
$$$0[111]010[011]0$$$
Clearly, the sum of 1s in these two intervals is 5.
Note that in this case the intervals are disjoint, but this is not a requirement.
