Đất nước Chuyên Sư phạm là một đất nước rộng lớn và phồn vinh với ~n~ trung tâm kinh tế lớn; để thuận tiện, các trung tâm kinh tế được đánh số từ ~1~ đến ~n~. Trước đây, vì để phát triển kinh tế, nhà nước đã xây dựng các con đường cao tốc (hai chiều) nối giữa các trung tâm kinh tế. Cụ thể hơn, giữa hai trung tâm kinh tế bất kỳ đều có một con đường, con đường nối giữa hai trung tâm kinh tế ~u~ và ~v~ có độ dài là ~w~ km.

Vì quy hoạch trong quá khứ không hợp lí, việc trung chuyển hàng hóa từ một trung tâm kinh tế tới một trung tâm kinh tế khác có thể không đi qua cao tốc nối trực tiếp chúng mà đi vòng qua một số cao tốc khác nhằm giảm thiểu thời gian. Khi đi qua nhiều cao tốc, quãng đường phải di chuyển là tổng độ dài các cao tốc đi qua. Trong ví dụ dưới đây, nếu vận chuyển hàng hóa theo tuyến đường ~5\rightarrow 4\rightarrow 2\rightarrow 3~ thì quãng đường là ~8~, còn theo tuyến đường ~5\rightarrow 1\rightarrow 4\rightarrow 2\rightarrow 3~ thì quãng đường là ~12~.

Đảng và nhà nước Chuyên Sư phạm đã quyết định tiến lên một bước lớn trên con đường quá độ lên chủ nghĩa xã hội: Tách biệt kinh tế nhà nước và kinh tế ngoài nhà nước. Để làm được như vậy, nhà nước cần chia các trung tâm kinh tế ra làm hai nhóm là trung tâm kinh tế nhà nước và trung tâm kinh tế ngoài nhà nước, mỗi thành phần kinh tế chỉ hoạt động tại các trung tâm kinh tế thuộc nhóm tương ứng.

Quãng đường trung chuyển hàng hóa của một nhóm kinh tế được định nghĩa là quãng đường trung chuyển hàng hóa lớn nhất giữa hai trung tâm thuộc nhóm đó. Nhà nước cần phân nhóm các trung tâm kinh tế sao cho tổng quãng đường trung chuyển hàng hóa của hai nhóm thành phần kinh tế là bé nhất có thể. Nói cách khác, nếu gọi ~A~ là quãng đường trung chuyển hàng hóa của nhóm kinh tế nhà nước, ~B~ là quãng đường trung chuyển hàng hóa của nhóm kinh tế ngoài nhà nước, ta cần cực tiểu hóa ~A+B~.

Yêu cầu: Bạn hãy giúp Đảng và nhà nước Chuyên Sư phạm tìm cách phân nhóm tốt nhất nhé.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ (~n\le 400~) là số trung tâm kinh tế trong đất nước Chuyên Sư phạm.

~n-1~ dòng tiếp, dòng thứ ~i~ chứa các số nguyên ~d_{i,i+1}, d_{i,i+2},..., d_{i,n}~ (~0\le d_{i,j}\le 10^9~), trong đó ~d_{i,j}~ là độ dài con đường nối giữa hai trung tâm kinh tế ~i~ và ~j~.

Output

In ra một số nguyên duy nhất là tổng quãng đường trung chuyển hàng hóa trong phương án tìm được.

Scoring

Có ~20\%~ số điểm của bài với ~n\le 20~

Có ~30\%~ số điểm khác với ~n\le 40~

Có ~20\%~ số điểm khác với ~n\le 200~

Còn lại không có điều kiện gì thêm

Sample Input 1

5
2 5 7 6
9 8 4
2 6
4

Sample Output 1

7

Notes

Trong test ví dụ, ta chia các trung tâm kinh tế thành 2 nhóm: ~\{2\}~ và ~\{1, 3, 4, 5\}~. Khi đó tổng quãng đường trung chuyển của nhóm đầu tiên là ~0~ và quãng đường trung chuyển của nhóm thứ hai là ~7~, tổng là ~7~.