Background

Thanks to

ing an approach better than the standard solution.

Problem Description

This problem has a large input size. It is recommended to use a fast input method. You may refer to the contest announcement board.

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$).

Input Format

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 Format

Output one number: the minimized value of $\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

见附件

见附件

Hint

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