P8088 "JROI-5" Autumn

Thanks to @[Wang Xiwen](/user/353688) for providing an approach better than the standard solution.

**This problem has a large input size. It is recommended to use a fast input method. You may refer to the [contest announcement board](https://www.luogu.com.cn/paste/lueudpd5).** You are given $n$ sequences, each with $m$ elements. The $j$-th element of the $i$-th sequence is the positive integer $a_{i,j}$. Each time, you may choose $(i_1, j_1)$ and $(i_2, j_2)$, and swap $a_{i_1,j_1}$ and $a_{i_2,j_2}$. You can perform at most $x$ swaps. Define $d_i$ as the $k$-th largest element in the $i$-th sequence. Minimize $\max\limits_{i=1}^n \{d_i\}$ (i.e., the maximum among $d_1, d_2, \cdots, d_n$).

The first line contains two positive integers $n, m$. The next $n$ lines each contain $m$ positive integers, representing the sequences. The last line contains two positive integers $k, x$.

Output one number: the minimized value of $\max\limits_{i=1}^n \{d_i\}$.

For Sample 1, swap $a_{2,5}$ and $a_{1,5}$. It can be proven that there is no better strategy. *** For $30\%$ of the testdata, $x = 10^6$, $1 \leq k \leq m$. For another $10\%$ of the testdata, **all numbers are equal**. For another $30\%$ of the testdata, $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$. For $100\%$ of the testdata, $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$。 Translated by ChatGPT 5