题目描述

给你一个 $n$ 行 $m$ 列的数字矩阵和一个正整数 $k$，第 $i$ 行第 $j$ 列的数称为 $a_{i,j}$。

求最小的非负整数 $x$，满足 $\sum_{i=1}^n \sum_{j=1}^m [\sum_{k=1}^n \sum_{l=1}^m (a_{k,l}-x) \times [k=i \operatorname{or} l=j]\le 0] \ge k$，其中 $[\text{condition}]$ 当且仅当 $\text{condition}$ 为真时等于 $1$，否则为 $0$。

形式化地，求最小的非负整数 $x$，使得矩阵中所有元素都减去 $x$ 之后，有至少 $k$ 格满足该格元素和所有与其同行或同列的元素之和小于等于 $0$。

输入格式

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

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行的第 $j$ 个整数表示 $a_{i,j}$。

输出格式

输出一行一个整数表示最小的非负整数 $x$。

2 3 1
1 2 3
4 5 6

3

提示

对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 3 \times 10^3$，$1 \leq k \leq n \times m$，$0 \leq a_i \leq 10^{11}$。