The Chief Engineer Peter was asked to develop a new model of aircraft for the company "Air Bubundiya". It was found that the hardest part is choosing the optimal size of the fuel tank.

The Chief Cartographer of "Air Bubundiya" John has made a detailed map of Bubundiya. On this map he marked the fuel consumption for the flight between each pair of cities.

Peter wants to make the size of fuel tank as small as possible, so that the aircraft can fly from any city to any other(possibly with refueling in cities on the way) .

Input

The first line contains the number of cities n (1 ≤ n ≤ 1000) in Burbundiya. Each of the next n lines contains n numbers. The j-th number in the i-th line equals to fuel consumption during the flight from i-th city to the j-th. All numbers are nonnegative and less than 109. It is known that for any i the number at the i-th line and the i-th position is zero.

Output

Print one number - the optimal size of the fuel tank.