← 返回题目列表

Codeforces · 873/C

C. 矩阵上的奇怪游戏

中文机器翻译题面 查看原题

Ivan 正在玩一个奇怪的游戏。

他有一个 n 行 m 列的矩阵 a。矩阵的每个元素等于 0 或 1。行和列的索引为 1。 Ivan 可以用零替换该矩阵中任意数量的 1。之后,他在比赛中的得分将计算如下:

1. 初始 Ivan 的得分为 0;
2. 在每一列中,Ivan 都会找到最上面的 1(也就是说,如果当前列是 j,那么他会找到满足 ai, j = 1 的最小 i)。如果该列中没有 1,则跳过该列;
3. Ivan 将查看该列中接下来的 min(k, n - i + 1) 个元素(从他找到的元素开始),并计算这些元素中 1 的数量。这个数字将被添加到他的分数中。

当然,伊万想在这场奇怪的游戏中最大化他的分数。而且他不想改变很多元素,所以他会用零替换尽可能少的个数。帮助他确定他可以获得的最大可能分数以及达到该分数所需的最小可能替换数量。

输入

第一行包含三个整数 n、m 和 k (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100)。

接下来是n行,其中第i行包含m个整数——矩阵a第i行的元素。每个数字要么是 0,要么是 1。

输出

打印两个数字:Ivan 可以获得的最大可能分数以及获得该分数所需的最少替换次数。

示例

输入 #1

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

输出 #1

4 1

输入 #2

3 2 1
1 0
0 1
0 0

输出 #2

2 0

注意

在第一个示例中,Ivan 将替换元素 a1, 2。