妙蛙种子站在一个满是地洞的场地旁。场地中有 $n \cdot k$ 个洞，被分成了 $n$ 组，每组包含 $k$ 个洞。组的编号从 $1$ 到 $n$，每组内的洞编号从 $1$ 到 $k$。在这些洞之间还有一些单向隧道。对于任意 $i \in [1, n-1]$，隧道只能连接第 $i$ 组的洞和第 $i+1$ 组的洞。

妙蛙种子想要用它的藤蔓穿过这些洞和隧道。它的藤蔓可以进入任意一个洞，穿过隧道，最后停在另一个洞中（过程中不会离开地面）。每一条被占用的隧道必须是从编号较小的组指向编号较大的组。由于洞和隧道比较狭窄，在任何时刻，每个洞或每条隧道中最多只能有一根藤蔓。

令 $f(i, j)$ 表示妙蛙种子能同时放入第 $i$ 组中某些洞内，并能到达第 $j$ 组中某些洞的藤蔓的最大数量。

你的任务是计算： $$\sum_{i=1}^{n} \sum_{j=i+1}^{n} f(i, j)$$

输入格式

第一行包含两个整数 $n$ 和 $k$ ($2 \le n \le 40\,000, 1 \le k \le 9$)，分别表示组的数量和每组中洞的数量。

接下来的 $n-1$ 个数据块描述了相邻组之间的连接情况。

每个数据块包含 $k$ 行，每行包含 $k$ 个字符。数据块之间由单个空行分隔。

如果第 $i$ 组的第 $p$ 个洞与第 $i+1$ 组的第 $q$ 个洞之间有隧道，则第 $i$ 个数据块的第 $p$ 行中的第 $q$ 个字符为 '1'。否则，该字符为 '0'。

输出格式

输出题目描述中要求的总和。

样例

样例输入 1

4 4
1000
1100
0110
0011

0100
1100
0010
0001

1000
1100
0000
0011

样例输出 1

21

样例输入 2

5 3
000
100
010

000
100
010

010
101
010

010
101
010

样例输出 2

17

说明

下图展示了第一个样例测试，以及将 3 根藤蔓从第一组一直延伸到最后一组的一种方式：

每组中的洞按从下到上的顺序编号。无法使用 4 根藤蔓，因此 $f(1, 4)$ 等于 3。

在第二个样例测试中，$f(3, 4) = f(4, 5) = f(3, 5) = 2$，因为妙蛙种子在任何洞或隧道中不能拥有超过一根藤蔓。