Главного конструктора Петю попросили разработать новую модель самолета для компании "Air Бубундия". Оказалось, что самая сложная часть заключается в подборе оптимального размера топливного бака.

Главный картограф "Air Бубундия" Вася составил подробную карту Бубундии. На этой карте он отметил расход топлива для перелета между каждой парой городов.

Петя хочет сделать размер бака минимально возможным, для которого самолет сможет долететь от любого города в любой другой (возможно, с дозаправками в городах на пути следования).

Входные данные

Первая строка содержит количество городов в Бубундии n (1 ≤ n ≤ 1000). Далее идут n строк по n чисел каждая. j-ое число в i-ой строке равно расходу топлива при перелете из i-ого города в j-ый. Все числа не меньше нуля и меньше 109. Гарантируется, что для любого i в i-ой строке i-ое число равно нулю.

Выходные данные

Одно число - оптимальный размер бака.