#1261. GAME

Xét bảng số gồm ô, mỗi ô chứa một số nguyên có giá trị nằm trong đoạn .

Ví dụ:

Ta gọi điểm của bảng là tổng tất cả các tích của số trên dòng với số trên dòng tương ứng (cùng cột). Với bảng trên thì điểm bằng:

Ta có loại phép biến đổi bảng như sau: Tráo hai ô liên tiếp trên cùng một dòng cho nhau, điều kiện để thực hiện được phép tráo là một ô phải khác và ô còn lại phải bằng .

Yêu cầu: Cho bảng số, hãy biến đổi bảng để được bảng có điểm là lớn nhất.

Dữ liệu vào:

• Dòng đầu là số ;
• Dòng thứ hai chứa số nguyên là số được ghi trên dòng của bảng số;
• Dòng thứ ba chứa số nguyên là số được ghi trên dòng của bảng số.

Dữ liệu ra:

• Gồm một số duy nhất là tổng điểm lớn nhất đạt được.

Ví dụ:

Dữ liệu vào:

7
-3 -1 -2 0 5 -1 0
0 -3 2 4 0 5 -2

Dữ liệu ra:

36

Giải thích:

Ta đưa bảng về như hình dưới đây: