Bạn là một người trẻ tuổi siêu tài năng và được làm việc trong vũ trụ, hôm nay bạn đang điều khiển một chiếc tàu không gian đi qua vũ trụ của các đỉnh trong một đồ thị vô hướng, nơi mỗi hành tinh được biểu diễn bởi một đỉnh và khoảng cách giữa chúng được ghi lại qua ma trận. Nhiệm vụ của bạn là khám phá xem từ đỉnh nào, tổng khoảng cách ngắn nhất đến tất cả các đỉnh còn lại lại lớn nhất. Cụ thể, bạn cần tính tổng các đường đi ngắn nhất từ mỗi đỉnh ~i~ đến tất cả các đỉnh khác (gọi là ~S_i~) và tìm ra giá trị lớn nhất trong số các ~S_i~.

Đặc biệt: Đề bài đảm bảo rằng đồ thị luôn có một ma trận đường đi ngắn nhất hợp lệ.

Input

• Dòng đầu: Số nguyên ~N~ (với ~N ≤ 500~) thể hiện số đỉnh của đồ thị.
• ~N~ dòng sau: Mỗi dòng gồm ~N~ số nguyên dương (không vượt quá ~10^9~) biểu diễn ma trận khoảng cách, trong đó số ở hàng ~u~ cột ~v~ đại diện cho khoảng cách từ đỉnh ~u~ đến đỉnh ~v~.

Output

• Một số nguyên dương duy nhất, là giá trị lớn nhất của ~S_i~ (tổng các đường đi ngắn nhất từ đỉnh ~i~ đến tất cả các đỉnh còn lại).

Sample Input

5
0 1 1 2 3 
1 0 5 2 2 
1 5 0 1 2 
2 2 1 0 4 
3 2 2 4 0

Sample Output

10

Notes

• Ma trận đường đi ngắn nhất sau khi xử lý có thể được biểu diễn như sau:
  • 0 1 1 2 3 -> ~S₁ = 7~
  • 1 0 2 2 2 -> ~S₂ = 6~
  • 1 2 0 1 2 -> ~S₃ = 6~
  • 2 2 1 0 3 -> ~S₄ = 7~
  • 3 2 2 3 0 -> ~S₅ = 10~