3*N 크기의 격자 모양 테이블이 주어집니다. 이 테이블의 각 칸에는 양의 정수 또는 음의 정수가 기록되어 있습니다.

당신은 다음 제약 조건을 모두 만족하도록 테이블의 칸에 조약돌을 배치해야 합니다.

[제약 조건]

1. 가로나 세로로 서로 인접한 두 칸에 동시에 조약돌을 놓을 수 없습니다.
2. 각 열(Column)에는 적어도 하나 이상의 조약돌을 놓아야 합니다. (즉, 조약돌을 하나도 놓지 않고 건너뛰는 열이 있어서는 안 됩니다.)

이 제약 조건을 지키며 조약돌을 놓았을 때, 조약돌이 놓인 자리에 있는 수들의 합을 최대가 되도록 하는 프로그램을 작성하시오.

입력

첫째 줄에 테이블의 열의 개수 N이 주어진다.

둘째 줄부터 넷째 줄까지 세 줄에 걸쳐 각 행의 원소 N개가 공백을 사이에 두고 주어진다.

출력

제약 조건을 만족하면서 조약돌을 놓았을 때, 얻을 수 있는 점수 합의 최댓값을 첫째 줄에 출력한다.

제한 사항

• 1 ≤ N ≤ 100,000
• 테이블의 각 칸에 적힌 수는 -10,000 이상 10,000 이하의 정수이다.

예제 입력 1

4
6 -1 5 3
-2 10 4 7
3 1 8 -5

예제 출력 1

39