숫자 박스

숫자 박스는 위쪽 행과 아래쪽 행, 그리고 N개의 열로 이루어진다. 전체 칸 수는 2N개이며, 각 칸은 비어 있거나 -10 이상 10 이하의 0이 아닌 정수가 적힌 숫자판 하나를 담을 수 있다.

아래 표는 N = 7일 때 가능한 한 숫자 박스의 상태이다. 빈칸은 숫자판이 없는 칸을 뜻한다.

숫자 박스의 값은 각 열마다 위쪽 칸과 아래쪽 칸의 값을 곱한 뒤, 그 값을 모두 더한 값이다. 빈칸은 0으로 계산한다. 위 표의 값은 (-3)×0 + (-1)×(-3) + (-2)×2 + 0×4 + 5×0 + (-1)×5 + 0×(-2) = -6이다.

각 행의 숫자판은 같은 행 안에서의 상대적인 순서를 유지한 채 빈칸으로 좌우 이동할 수 있다. 숫자판이 서로를 건너뛰거나 자리를 바꿀 수는 없다. 예를 들어 위쪽 행의 5와 -1을 각각 오른쪽으로 한 칸씩 옮기고, 아래쪽 행의 -3을 왼쪽으로 한 칸, 2와 4를 각각 오른쪽으로 한 칸씩 옮기면 다음과 같은 박스를 만들 수 있다.

이 박스의 값은 9 + 25 + 2 = 36이다.

초기 숫자 박스가 주어졌을 때, 각 행의 숫자판 순서를 유지하면서 가로로 이동해 만들 수 있는 숫자 박스의 값 중 최댓값을 구하시오.

첫 줄에 숫자 박스의 열 수를 나타내는 정수 N (1 <= N <= 400)이 주어진다.

다음 두 줄에는 초기 숫자 박스의 위쪽 행과 아래쪽 행이 차례로 주어진다. 각 줄에는 N개의 정수가 있으며, 0은 숫자판이 없는 빈칸을 뜻한다. 숫자판에 적힌 값은 모두 -10 이상 10 이하의 0이 아닌 정수이다.

숫자판을 이동해 얻을 수 있는 숫자 박스의 값의 최댓값을 출력한다.