#1617. [语言月赛 202307] 魔法少女扶苏

[语言月赛 202307] 魔法少女扶苏

题目描述

给定一个 nn 行 mm 列的数字矩阵,第 ii 行第 jj 列的数称为 ai,ja_{i,j}。

扶苏可以释放任意多次魔法,每次施放魔法,矩阵里的每个数字都会被减去 11。

现在扶苏想知道,她至少需要释放几次魔法,才能让矩阵中存在至少 kk 个位置 (x,y)(x, y),满足 ax,ya_{x, y} 大于或等于它所在行和列的元素之和。

形式化地,你需要计算最小的魔法释放次数使得施放魔法后存在至少 kk 个位置 (x,y)(x, y),满足 $a_{x, y} \geq \sum \limits _{i = 1}^n a_{i,y} + \sum \limits _{i = 1}^m a_{x,i}$。

输入格式

第一行是三个整数,表示矩阵的行数 nn,列数 mm 和要求符合条件的位置个数 kk。

接下来 nn 行,每行 mm 个整数,第 ii 行的第 jj 个整数表示初始的 ai,ja_{i,j}。

输出格式

输出一行一个整数表示答案。

样例

2 3 1
1 2 3
4 5 6
3

题目来源:洛谷 B3811