Flights#1936
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 required for the flight between each pair of cities.
Peter wants to make the size of the fuel tank as small as possible, so that the aircraft can fly from any city to any other (possibly with refueling in cities along the way).
The first line contains the number of cities (1 \leq n \leq 1000) in Bubundiya. Each of the next lines contains numbers. The -th number in the -th line equals the fuel consumption for the flight from the -th city to the -th. All numbers are nonnegative and less than 10^9. It is guaranteed that for any , the -th number in the -th line is .
Print one number — the optimal size of the fuel tank.
Example 1