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

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

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

Вхідні дані

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

Вихідні дані

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