题目描述

题目译自 XXV Olimpiada Informatyczna — I etap Różnorodność

给你一个由 $m$ 行 $n$ 列整数组成的二维矩阵 $A$。我们把矩阵 $A$ 中 $k \times k$ 大小的子矩阵称为 $k$-片段。

$k$-片段的多样性定义为其不同元素的个数。你的任务是找出所有 $k$-片段中最大的多样性，以及所有 $k$-片段多样性的总和。

输入格式

输入的第一行包含三个正整数 $m, n, k$ $(k \leq \min(m, n))$，分别表示矩阵的行数、列数和 $k$-片段的大小。

接下来的 $m$ 行，每行 $n$ 个整数，表示矩阵 $A$ 的元素，范围在 $[1, C]$ 内，各数字用空格分隔。

输出格式

输出一行，包含两个整数（用空格分隔）：所有 $k$-片段的最大多样性，以及所有 $k$-片段多样性的总和。

3 5 2
1 5 3 3 3
4 1 3 3 4
4 2 4 4 3

4 20

从上到下、从左到右的 $2$-片段多样性依次为：第一行 $3$、$3$、$1$、$2$，第二行 $3$、$4$、$2$、$2$，总和为 $20$。

附加样例

1. $m=3, n=3, k=2$，小型正确性样例；
2. $m=20, n=100, k=10$，矩阵中每个数字为行号与列号之和；
3. $m=1000, n=k=1$，矩阵中每个数字都相同；
4. $m=n=k=200$，矩阵中每个数字都不同；
5. $m=n=3000, k=1000$，矩阵中每个数字为行号与列号之和。

数据范围与提示

详细子任务附加限制及分值如下表所示。