Tý có đa giác lồi \(N\) cạnh, mỗi cạnh i có trọng số \(w_i\). Chọn một tập các cạnh không kề nhau (không chung đỉnh) sao cho tổng trọng số lớn nhất. Đa giác có dạng vòng tròn, cạnh \(N-1\) và cạnh \(0\) cũng kề nhau.

#

Định dạng đầu vào

• Dòng 1: Số nguyên \(N\) (\(3 \le N \le 500\)).
• \(N\) dòng tiếp theo: mỗi dòng chứa N số nguyên là ma trận trọng số \(W_{i,j}\).

Định dạng đầu ra

• In ra tổng trọng số lớn nhất chọn được.

Ví dụ

Input:

3
0 2 3
2 0 4
3 4 0

Output:

7

Giải thích: Chọn các cạnh tối ưu không giao nhau bên trong.

Ràng buộc & Subtasks