题目描述

妙蛙种子来到一片布满地洞的草地。这里共有 $n\cdot k$ 个洞，被分成 $n$ 组，每组恰好有 $k$ 个洞。组从 $1$ 到 $n$ 编号，每组内的洞从 $1$ 到 $k$ 编号。

相邻两组之间可能有一些单向隧道。对于每个 $i\in[1,n-1]$，隧道只可能从第 $i$ 组的某个洞通向第 $i+1$ 组的某个洞，不会跨越更多组，也不会反向。

妙蛙种子想把若干条藤蔓伸入这些洞和隧道中。一条藤蔓可以从任意一个洞进入，沿着隧道前进，并在另一个洞中结束，全程不需要钻出地面。每条被使用的隧道必须从编号较小的组指向编号较大的组。由于洞和隧道都很狭窄，同一时刻任意一个洞或任意一条隧道中至多只能有一条藤蔓。

定义 $f(i,j)$ 为：妙蛙种子最多能同时从第 $i$ 组的一些洞中放入多少条藤蔓，使这些藤蔓最终到达第 $j$ 组的洞。

请计算

输入格式

第一行包含两个整数 $n,k$，分别表示组数和每组洞的数量。

接下来有 $n-1$ 个块，依次描述相邻组之间的连接情况。每个块包含 $k$ 行，每行包含 $k$ 个字符。相邻两个块之间用一个空行分隔。

对于第 $i$ 个块，如果第 $i$ 组第 $p$ 个洞到第 $i+1$ 组第 $q$ 个洞之间存在隧道，则该块第 $p$ 行第 $q$ 个字符为 1；否则为 0。

输出格式

输出一行一个整数，表示题目中定义的总和。

数据范围

• $2\le n\le 40000$；
• $1\le k\le 9$。

样例 1

输入

4 4
1000
1100
0110
0011

0100
1100
0010
0001

1000
1100
0000
0011

输出

21

样例 2

输入

5 3
000
100
010

000
100
010

010
101
010

010
101
010

输出

17

解释

$4$ 组、每组 $4$ 个洞，洞在每组中自下而上编号；用有向连线表示相邻组之间的隧道，并画出一种从第 $1$ 组到第 $4$ 组同时放入 $3$ 条藤蔓的方案。

在第一组样例中，每组内的洞按从下到上的顺序编号。不可能同时使用 $4$ 条藤蔓从第 $1$ 组到达第 $4$ 组，因此 $f(1,4)=3$。

在第二组样例中，由于任意洞或隧道中至多只能有一条藤蔓，有 $f(3,4)=f(4,5)=f(3,5)=2$。