题目描述

一个 $n\times m$ 的棋盘，每格被涂成黑色或白色。输入用一个 01 矩阵描述：第 $i$ 行第 $j$ 列是 0 表示白格，1 表示黑格。

现在要选一个 $k\times k$ 的方形区域，把这块区域里的格子全部改成同一种颜色（改成黑色或白色都行）。改一个格子的代价是 $1$。

求最小的总代价。

输入格式

第一行三个整数 $n,m,k$。

接下来 $n$ 行，每行一个长度为 $m$ 的 01 串。

输出格式

一行一个整数，表示最小代价。

输入输出样例 #1

输入 #1

3 4 2
0101
1010
0101

输出 #1

2

说明

数据范围

• 对于 $100\%$ 的数据，$1\le k\le n,m\le 2\times 10^3$，$n\times m\le 4\times 10^6$。