You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

感谢 @王熙文 提供了一种优于标算的做法。

题目描述

本题读入量较大，建议使用较快的读入方式，可以参考 赛时公告板

给定 $n$ 个数列，每个数列有 $m$ 个元素，第 $i$ 个数列第 $j$ 个元素为正整数 $a_{i,j}$。

你每次可以选择 $i_1,j_1$ 和 $i_2,j_2$，交换 $a_{i_1,j_1}$ 和 $a_{i_2,j_2}$。你至多可以进行 $x$ 次交换。

定义 $d_i$ 为第 $i$ 个数列中第 $k$ 大的元素。

请最小化 $\max\limits_{i=1}^n \{d_i\}$。（表示 $d_1,d_2,\cdots,d_n$ 中的最大值）

输入格式

第一行两个正整数 $n,m$。

接下来 $n$ 行每行 $m$ 个正整数，表示数列。

最后一行两个正整数 $k,x$。

输出格式

一行一个数，输出最小化的 $\max\limits_{i=1}^n \{d_i\}$。

5 5
1 2 3 4 5
6 7 8 9 10
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
2 1

8

5 5
1 2 3 4 5
6 7 8 9 10
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
2 2

7

见附件

见附件

提示

对于样例 1，将 $a_{2,5}$ 和 $a_{1,5}$ 交换，可以证明，没有更优策略。

对于 $30\%$ 的数据，$x = 10^6,1\leq k\leq m$。

对于另外 $10\%$ 的数据，所有的数都相等。

对于另外 $30\%$ 的数据，$1\leq n,m\leq 2\times 10^3,1\leq k\leq m,a_{i,j}\leq 10^6,0\leq x\leq n\times m$。

对于 $100\%$ 的数据，$1\leq n,m\leq 2\times 10^3,1\leq k\leq m,1\leq a_{i,j}\leq 10^{18},0\leq x\leq n\times m$。