Xét bảng số gồm \(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 bảng là tổng tất cả các tích của số trên dòng \(1\), số trên dòng \(2\) và số trên dòng \(3\) 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 \(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.

Input

• 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ố.

Output

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

Example

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

36

Constraints

• Giá trị tuyệt đối của mỗi số trong bảng không vượt quá \(100\).
• Subtask \(1\) (\(20\%\) số điểm): \(n \le 5\) và các số ghi trên dòng thứ ba đều bằng \(1\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 5\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 10\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 100\) và các số ghi trên dòng thứ ba đều bằng \(1\).
• Subtask \(5\) (\(20\%\) số điểm): \(n \le 100\).