Matrix

You are given an N×N matrix of numbers.

Your task is to choose N numbers such that each number comes from a different row and a different column. The goal is to minimize the largest number among the selected ones.

Input

The input begins with an integer N (1 ≤ N ≤ 100), followed by N^2 non-negative integers, each not greater than 20000.

Output

Print the smallest possible value of the largest number among the selected numbers.

Examples