给你一个长度为 $n$ 且仅由数字 0–9 组成的字符串 $S$。你想用这个字符串来生成一个扫雷游戏的变体。在这个变体中，一个格子可以包含多于一颗地雷，并且一个格子中的地雷计数是基于其 4-邻域（边相邻的格子）计算的，而不是通常的 8-邻域。

为此，你选择一个整数 $w$ ($1 \le w \le n$) 作为网格的宽度。你将这 $n$ 个编号为 $0$ 到 $n - 1$ 的格子排列成一个网格。该网格有 $\lceil n/w \rceil$ 行，从上到下编号为 $0$ 到 $\lceil n/w \rceil - 1$；有 $w$ 列，从左到右编号为 $0$ 到 $w - 1$。对于每个 $0 \le i < n$，格子 $i$ 位于第 $\lfloor i/w \rfloor$ 行、第 $i \bmod w$ 列，并对应 $S$ 的第 $i + 1$ 个字符（数字）。因此，第 0 行包含格子 $0$ 到 $w - 1$，第 1 行包含格子 $w$ 到 $2w - 1$，依此类推。注意，最下面的一行包含的格子数可能少于 $w$ 个。

排列好网格后，你执行以下步骤：

1. 对于每个对应非零数字 $x$ (1–9) 的格子，你在该格子中放置 $x$ 颗地雷。
2. 对于每个对应数字 0 的剩余格子，你在该格子中写下一个数字，该数字等于其相邻格子中地雷的总数。如果两个格子共享一条边，则称它们是相邻的。注意，每个格子最多有四个相邻格子。

对于宽度 $w$，定义 $f(w)$ 为生成的网格上所有没有地雷的格子中数字的总和。给定一个整数 $k$，你的任务是计算 $f(1), f(2), \dots, f(n)$ 中第 $k$ 大的值。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$ ($1 \le k \le n \le 500\,000$)。

第二行包含一个长度为 $n$ 且仅由数字 0–9 组成的字符串 $S$。

输出格式

输出 $f(1), f(2), \dots, f(n)$ 中的第 $k$ 大的值。

样例

输入格式 1

5 3
20103

输出格式 1

7

说明

图 F.1 展示了宽度为 1 到 5 时生成的网格。格子中的每个圆点代表一颗地雷。

图 F.1：所有 5 种可能宽度的生成网格。

通过将不含地雷的格子上的数字相加，可以得到：

• $f(1) = 7$
• $f(2) = 3$
• $f(3) = 11$
• $f(4) = 4$
• $f(5) = 7$

其中第 3 大的值为 7。

输入格式 2

5 1
20103

输出格式 2

11

输入格式 3

8 4
60409003

输出格式 3

35