Guaranteed Victory in Three Kingdoms

In the game Three Kingdoms, there are N generals (where N is an even integer and N \ge 4). For every two distinct generals i and j, there is a unique synergy value \(S_{i,j}\) (rendered in \(\LaTeX\) as \(S_{i,j}\)) representing the combined combat power when these two are paired.

At the start, all generals are free. The game then proceeds in a drafting phase. The process is as follows:

• The player selects one free general first.
• Then the computer selects one free general.
• The turns alternate (player \(\to\) computer \(\to\) player \(\to\) computer, ... ) until all the generals have been chosen. Consequently, each side will have exactly \(\frac{N}{2}\) generals.

After drafting, each side chooses a pair of generals from their team whose synergy is the highest among all pairs within the team. The two teams then pit their best pairs against each other. The team whose best-pair synergy is higher wins the battle.

The computer follows a fixed strategy when it is its turn. Specifically, at any moment when the computer must choose, it does the following: for every general in the player’s current team and every free general, it considers the pair (player general, free general) and finds the pair with the highest synergy. The computer then selects the free general that appears in that highest-scoring pair, thereby trying to preclude the player from obtaining a very synergistic pairing.

The player wonders: assuming the computer always uses this strategy, is there a way for the player to guarantee victory? If so, among all scenarios in which the player wins, what is the maximum possible synergy value of the pair chosen from the player’s team for battle? If no winning strategy exists, output -1.

Note: It is guaranteed that the synergy values for different pairs are distinct. All formulas are written in \(\LaTeX\) format (for example, \(\LaTeX\) for formulas such as \(N \ge 4\), \(S_{i,j}\), etc.).

inputFormat

The input begins with a line containing an even integer \(N\) (\(N \ge 4\)), which is the number of generals. The next \(N\) lines each contain \(N\) integers. The \(j\)th integer in the \(i\)th line represents the synergy value \(S_{i,j}\) between generals \(i\) and \(j\). It is guaranteed that for any two distinct pairs \((i,j)\) and \((k,l)\), \(S_{i,j}\) and \(S_{k,l}\) are different.

outputFormat

Output a single integer: the maximum possible synergy value from the player’s team pair (i.e. the maximum synergy among all pairs in the player’s team) achievable under a winning strategy. If no winning strategy exists, output -1.

sample

4
0 10 20 30
10 0 40 50
20 40 0 60
30 50 60 0

50