Sau lễ thành hôn của Tấm là các trò chơi dân gian của vương quốc, một trong những trò chơi được ưa chuộng là trò chơi bảng số diễn ra như sau:

Xét bảng số gồm \(\mathbf{3 \times n}\) ô, mỗi ô chứa một số nguyên có giá trị tuyệt đối không vượt quá 100.

Ví dụ:

Ta gọi điểm của mỗi cột là tích của ba số trong cột đó, điểm của bảng là tổng tất cả điểm của các cột. Với bảng trên thì điểm bằng:

(-3)×(0)×(1) + (-1)×(-3)×(1) + (-2)×(2)×(1) + (0)×(4)×(1) + (5)×(0)×(1) + (-1)×(5)×(1) = -6

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 0 và ô còn lại phải bằng 0.

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ố \(n;\)

• Dòng thứ hai chứa \(n\) số nguyên là \(n\) số được ghi trên dòng 1 của bảng số;

• Dòng thứ ba chứa \(n\) số nguyên là \(n\) số được ghi trên dòng 2 của bảng số;

• Dòng thứ tư chứa \(n\) số nguyên là \(n\) số được ghi trên dòng 3 của bảng số.

Kết quả: Ghi một dòng chứa một số duy nhất là tổng điểm lớn nhất đạt được.

Ví dụ:

Ràng buộc:

• Có 20% số test ứng với 20% số điểm của bài có \(n \leq 5\) và các số ghi trên dòng thứ ba đều bằng 1;

• Có 20% test khác ứng với 20% số điểm của bài có \(n \leq 5\);

• Có 20% test khác ứng với 20% số điểm của bài có \(n \leq 10;\)

• Có 20% test khác ứng với 20% số điểm của bài có \(n \leq 100\) và các số ghi trên dòng thứ ba đều bằng 1;

• Có 20% số test còn lại ứng với 20% số điểm của bài có \(n \leq 100.\)