Optimal Token Selection

You are given a grid with n rows and m columns, where each cell contains a token with an integer value. Two players, Vova and Lesha, take turns picking tokens. They always pick the token with the highest available value until no moves remain. If the total number of tokens is even, both players pick exactly \(\frac{n\times m}{2}\) tokens, otherwise one token remains at the end. Your task is to compute the minimal value among the remaining tokens after both players have played optimally.

Formally, let \(T\) be the multiset of token values. After sorting \(T\) in ascending order and removing the top \(2\times\lfloor\frac{n\times m}{2}\rfloor\) tokens (i.e. the tokens that the players pick), the answer is defined as:

[ answer = \begin{cases} \min{t \in T'} & \text{if } T' \neq \emptyset,\ t_{min} & \text{otherwise, where } t_{min} \text{ is the smallest token in } T. \end{cases} ]

It is guaranteed that the input is structured so that both players pick tokens optimally.

inputFormat

The first line contains two space-separated integers n and m (\(1 \le n, m \le 1000\)), representing the number of rows and columns respectively. Each of the following n lines contains m space-separated integers, representing the token values in that row.

outputFormat

Output a single integer — the minimal value of any remaining token after both players have picked tokens optimally.

3 3
3 1 4
1 5 9
2 6 5

1