32931번 - 자석 놀이

문제

2ドル \times N$ 크기의 격자가 있다. 격자의 각 칸에는 수가 적힌 카드가 하나씩 있다. 맨 왼쪽 위에는 자석이 있고 당신은 이 자석을 상하좌우로 한 칸씩 움직여 맨 오른쪽 아래로 이동시키려고 한다.

자석이 카드 위를 지나면 카드는 자석에 달라붙게 되며, 한 번 붙은 카드는 자석에서 다시 떨어지지 않는다. 자석을 맨 오른쪽 아래까지 이동시켰을 때 자석에 붙은 카드에 적힌 수의 합의 최댓값을 구해보자.

입력

첫 번째 줄에 격자의 열의 개수를 나타내는 수인 $N$이 주어진다. $(2 \leq N \leq 200\ 000)$

다음 두 줄에 걸쳐 카드에 적힌 수가 공백으로 구분되어 주어진다. $i+1$번째 줄의 $j$번째 수 $a_{ij}$는 $i$번째 행의 $j$번째 열에 있는 카드에 적힌 수를 나타낸다. $(-10^9 \leq a_{ij} \leq 10^9)$

출력

문제의 답을 출력한다.

제한

힌트

맨 오른쪽 아래 칸을 포함해, 자석이 한 번 지나간 칸을 다시 지나갈 수 있음에 유의하라.