题目描述

现在有一个$n$行$m$列的矩阵。

从第一行到第$n$行，你可以执行下列操作一次（即不能对同一行反复执行操作）：

对于当前的第$i$行，将这一行上的所有数字加上$a_i$。其中$0 \le a_i \le k$。

你的任务是：

1. 使得相邻的（上下或者左右相邻）的数字相等的数量最少；
2. 在满足第一点的前提下，使得所有操作的$a_i$之和最小。

你的任务是求出最少的相邻相等数字数量以及最小的$a_i$之和。

输入格式

第一行三个整数$n, m, k$，表示矩阵大小为$n$行$m$列，$a_i$的限制为$0 \le a_i \le k$。

接下来$n$行，每行$m$个整数，构成这个矩阵。

输出格式

一行两个整数，第一个整数表示最少的相邻相等数字数量，第二个整数表示最小的$a_i$之和。

2 2 5
1 1
2 1

1 1

样例解释

对第二行加1，可以得到

1 1
3 2

此时只有第一行存在一组相邻相等的数字，这是使得相邻相等数字最少的方案；此时所有操作的$a_i$之和为1。

数据规模与约定

每组数据点10分，共10组数据。 对于所有数据，矩阵中的数字范围在$[1, 50]$之间。

大样例

大样例下载