Rất có thể bạn đã nghe nói về vấn đề người bán hàng lưu động. Nếu có thì bạn biết rằng đó là một bài toán NP khó vì nó thiếu giải pháp hiệu quả. Chà, nhiệm vụ này là một phiên bản không phổ biến của bài toán nổi tiếng! Sự không phổ biến của nó xuất phát từ thực tế là phiên bản này thực sự có thể giải được.

Người bán hàng đang thực hiện nhiệm vụ đi thăm ~N~ thành phố, mỗi thành phố đúng một lần. Các thành phố được biểu thị bằng các số ~1, 2, ..., N~. Những gì chúng ta biết là thời gian bay thẳng giữa mỗi cặp thành phố. Người bán hàng, vốn là người làm việc hiệu quả, muốn thay đổi trình tự tham quan thành phố sao cho tổng thời gian chuyến bay là tối thiểu có thể.

Than ôi, tất cả không đơn giản như vậy. Ngoài ra, người bán hàng còn có một điều kiện đặc biệt liên quan đến trình tự. Đối với mỗi thành phố được gắn nhãn ~K~ phải áp dụng: hoặc tất cả các thành phố có nhãn nhỏ hơn ~K~ đã được ghé thăm trước thành phố được gắn nhãn ~K~ hoặc tất cả chúng sẽ được ghé thăm sau thành phố được gắn nhãn ~K~. Nói cách khác, tình huống khi một trong những thành phố đó được ghé thăm trước đó, và cái sau không được phép.

Hỗ trợ anh chàng tội nghiệp trong sứ mệnh đầy tham vọng của mình và tính toán tổng thời gian bay tối thiểu cần thiết để đi đến tất cả các thành phố, bắt đầu từ bất kỳ thành phố nào và kết thúc ở bất kỳ thành phố nào, ghé thăm mỗi thành phố đúng một lần để yêu cầu đặc biệt của anh ta được thực hiện.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(2 \le N \le 1500)~, số thành phố.
• Mỗi dòng trong số ~N~ dòng tiếp theo chứa ~N~ số nguyên dương trong khoảng ~[0, 1000]~. Số ở vị trí ~B~ ở hàng ~A~ thể hiện thời gian bay giữa thành phố ~A~ và ~B~, số đó bằng số ~A~ ở hàng ~B~. Khi ~A = B~, số đó là ~0~. Ngược lại, nó là giá trị dương.

Output

• Dòng đầu tiên và duy nhất phải chứa tổng thời lượng chuyến bay tối thiểu được yêu cầu.

Scoring

• Trong dữ liệu kiểm tra chiếm ~1/3~ tổng số điểm, ~N~ sẽ tối đa là 10.
• Trong dữ liệu kiểm tra có giá trị bằng ~1/2~ tổng số điểm, ~N~ sẽ tối đa là 20.

Sample Input 1

3
0 5 2
5 0 4
2 4 0

Sample Output 1

7

Sample Input 2

4
0 15 7 8
15 0 16 9
7 16 0 12
8 9 12 0

Sample Output 2

31

Làm rõ ví dụ thứ nhất: Trình tự tối ưu là 2, 1, 3 hoặc 3, 1, 2. Trình tự 1, 3, 2 thậm chí còn thuận lợi hơn nhưng lại không đáp ứng được điều kiện của người bán hàng.

Làm rõ ví dụ thứ hai: Chuỗi là 3, 1, 2, 4 hoặc 4, 2, 1, 3.