N couples live on an island; each couple consists of a hunter and a farmer. They formed several committees. The Hunting Committee divided the island up into N hunting fields. Independently, the Farming Committee divided the island into N farms.
You, as the leader of the Distribution Committee, have to distribute hunting fields to hunters and farms to farmers. However, the Marriage Committee only accepts distributions where for each couple, their hunting field and farm have an intersection of positive area.
Find a distribution where the minimum of those intersections has the maximum possible value.

Input

The first line contains the value of N. The next N lines each contain N numbers separated by spaces that are the areas of the intersection of the ith hunting field and the jth farm (where i is the line number (minus one) and j is the index of the number in the line).

Output:

The minimum of the intersections.

This is the text variant of the problem. Read more here about submitting solutions!

Example

Input:
3
5 2 2
2 3 5
2 1 3

Output:
3