Giải bài trực tuyến

Hai quân xe được đặt tại hai ô khác nhau trên một bàn cờ vua có NxN ô. Mỗi ô của bàn cờ có một giá trị từ 0 đến 1000.

Một ô trong bàn cờ được gọi là bị tấn công nếu ô đó cùng hàng hoặc cùng cột với ít nhất một quân xe. Hai ô vuông có chứa quân xe được xem như không bị tấn công.

Bài toán đặt ra là tìm cách đặt hai quân xe lên bàn cờ, để tổng giá trị các ô bị tấn công là lớn nhất.

Dữ liệu

• Dòng 1: Số nguyên dương N (2 ≤ N ≤ 300).
• N dòng tiếp theo, mỗi dòng gồm N số. Đây là giá trị của các ô trên bàn cờ.

Kết quả

• Tổng lớn nhất tìm được.

Ví dụ

Giải thích

• Vị trí đặt hai quân xe trong ví dụ 1 là (1, 1) và (2, 2)
• Vị trí đặt hai quân xe trong ví dụ 2 là (1, 3) và (1, 4)
• Vị trí đặt hai quân xe trong ví dụ 3 là (2, 5) và (4, 3)

Giới hạn

• Có 60% số test, 2 ≤ N ≤ 100