题目描述

Lucia 很喜欢吃辣，但是现在她想尝试吃一次草莓蛋糕。

一个草莓蛋糕可以看成一个 $n$ 行 $m$ 列的矩阵 $a$，矩阵的第 $i$ 行第 $j$ 列会有一个参数 $a_{i,j}$，若 $a_{i,j}=1$，则表示这个位置有一颗草莓；否则 $a_{i,j}=0$，表示这个位置没有草莓。

Lucia 会以一定的位置顺序吃掉这个蛋糕。她会从第 $1$ 行第 $1$ 列开始向右，到第 $1$ 行第 $m$ 列后，再从第 $2$ 行第 $m$ 列开始向左，到第 $2$ 行第 $1$ 列，再从第 $3$ 行第 $1$ 列开始向右……以此类推。

比如对于一个 $4$ 行 $5$ 列的蛋糕，Lucia 吃掉的位置顺序如箭头所示：

当然 Lucia 的胃口不是很大。她会按照上述的顺序，先吃前 $d$ 个位置。此时若蛋糕还没被吃完，则假设她下一个要吃的位置是第 $x$ 行第 $y$ 列。如果她发现这个位置恰好有草莓，即 $a_{x,y}=1$，那么她会继续吃 $d$ 个位置；否则 $a_{x,y}=0$，她会停止吃蛋糕。在吃的过程中，如果蛋糕被吃完，则直接停止。

现在你需要求出，她依照上述过程，最终会吃掉多少颗草莓（即 $a_{i,j}=1$ 的位置的个数）？

输入格式

第一行三个正整数 $n,m,d$，用半角空格隔开。

下面 $n$ 行，每行 $m$ 个整数。第 $i+1$ 行第 $j$ 列的数为 $a_{i,j}$。

输出格式

一行一个正整数，即 Lucia 最终吃掉的草莓数量。

4 4 3
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

3

5 5 13
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0

12

4 5 7
0 0 0 0 0
0 1 1 1 0
1 1 0 1 0
0 1 1 1 0

6

提示

样例解释

对于样例 1，Lucia 首先会吃掉如下红色框出的位置：

此时下一个要吃的位置是第 $1$ 行第 $4$ 列（即绿色框出的位置），$a_{1,4}=1$，所以她会继续吃下去：

这时下一个要吃的位置是第 $2$ 行第 $2$ 列（即绿色框出的位置），$a_{2,2}=0$，所以 Lucia 会停止。最终吃掉了 $3$ 颗草莓。

对于样例 2，Lucia 会先吃掉如下红色框出的位置：

$a_{3,4}=1$，她会继续吃下去。然而剩余的位置数量少于 $d=13$，因此她会全部吃完。最终吃掉了所有的 $12$ 颗草莓。

数据范围

对于 $20\%$ 的数据，保证 $a_{i,j}=0$。

对于另外 $20\%$ 的数据，保证 $d=1$。

对于 $100\%$ 的数据，保证 $1\le n,m\le 500$，$1\le d\le n\times m$，$0\le a_{i,j}\le 1$。