题目描述

节日将至，小渠要在一条长廊上布置灯串。长廊有 $n$ 盏灯，从左到右编号 $1\sim n$。给定一个长度为 $n$ 的字符串 $s$：0 表示该位置的灯最开始是熄灭，1 表示最开始是点亮。

小渠可以把若干盏熄灭的灯点亮（把对应位置从 0 改成 1）。但只有连续两盏及以上的亮灯才算“成排的亮灯”。

你会得到 $q$ 个不同的询问，每次询问给出一个能点亮灯的盏数 $k_i$。请分别求出在最优方案下，“成排的亮灯”最多有多少盏。

输入格式

第一行两个整数 $n,q$。 第二行一个长度为 $n$ 的字符串 $s$（仅含 0 和 1）。 接下来 $q$ 行，每行一个整数 $k_i$（表示可把多少个 0 变为 1）。

输出格式

输出 $q$ 行，每行一个整数，表示对应 $k_i$ 下的“成排亮灯”最多数量。

输入输出样例 #1

输入 #1

3 4
000
0
1
2
3

输出 #1

0
0
2
3

输入输出样例 #2

输入 #2

4 3
1010
0
1
2

输出 #2

0
3
4

输入输出样例 #3

输入 #3

11 6
11010101001
5
2
0
1
4
3

输出 #3

11
7
2
5
10
9

数据范围

对于30%的数据：$1 \le n \le 2000$；$1 \le q \le n+1$；$0 \le k_i \le n$；$s \in {0,1}^n$

对于100%的数据：$1 \le n \le 10^5$；$1 \le q \le n+1$；$0 \le k_i \le n$；$s \in {0,1}^n$