Trees in the garden
The Central Garden in Olympia country is so big that one gardener can not maintain it. It was decided to divide the garden into two parts. Certain trees will be assigned to the first part, and the rest to the second. One part of the garden can remain empty.
Between each pair of trees in the garden the roads are trodden. When gardeners go from one tree to another, they go along the road directly connecting the two trees. The length of the path is the same when moving in both directions.
To simplify the work of gardeners, it was decided to divide the garden so that the length of the longest path between a pair of trees belonging to the same part is minimal.
Write a program that according to the information about the lengths of the paths between all pairs of trees, finds the length of the longest road between the trees from one part of the garden, when the garden has optimal division into two parts.
Input
The first line contains one integer n (2 ≤ n ≤ 1000) - the number of trees in the garden. Each i-th from the next n - 1 lines contains n - i numbers that gives the the road lengths between the i-th tree and trees from i + 1 to n-th. All numbers are non negative integers, not greater than 10^6.
Output
Print one integer - the minimum length of the longest road between the trees in one part of the garden for all possible partitions of the garden.