31027번 - 물고기 게임

문제

오토는 반쵸스시에서 곰치 커리를 대접받은 뒤, 그 보답으로 데이브에게 2ドル\times N$ 크기의 양식장을 만들어 주었다!

• 데이브: 오...! 여기는 뭔가요?
• 오토: 자네, 만날 물고기 잡아 오니라 꽤 고생하고 있는 것 같구먼?
• 오토: 그래서 내가 어제 하루 만에 뚝딱 이 양식장을 만들어 버렸잖여!
• 데이브: ... 하루 만에?
• 오토: 내가 일단 $(1, 1)$과 $(2, N)$을 제외한 칸 $(i, j)$에는 물고기를 $A_{i,j}$마리씩 넣어 놨구먼.
• 오토: 그런데 그냥 줄 수는 없쟈. 나랑 게임을 해서 자네가 얻은 만큼의 물고기를 주겠슈!

... 그렇게 해서 데이브와 오토가 게임을 하게 되었다. 오토는 $(1,1)$에 서 있고, 데이브는 $(2,N)$에 서 있다. $(1,1)$과 $(2,N)$을 제외한 칸에는 물고기가 있다. 데이브와 오토는 다음과 같은 턴을 10ドル^{100}$회 반복한다.

• 오토가 인접한 칸으로 이동한다.
• 오토가 그 칸에 있는 물고기를 모두 수확해 가져간다. 오토가 칸을 떠나도 물고기는 다시 생기지 않는다.
• 데이브가 인접한 칸으로 이동한다.
• 데이브가 그 칸에 있는 물고기를 모두 수확해 가져간다. 데이브가 칸을 떠나도 물고기는 다시 생기지 않는다.
• 이 과정에서 데이브와 오토는 같은 칸에 동시에 있을 수도 있다.

데이브와 오토는 물고기를 최대한 많이 가져가려고 한다. 이때, 오토가 가져가는 물고기의 마릿수와 데이브가 가져가는 물고기의 마릿수를 구해야 한다.

입력

첫 번째 줄에 양식장의 크기 $N$이 주어진다.

두 번째 줄에는 $A_{1,1}, A_{1, 2}, \cdots A_{1, N}$가 공백으로 구분되어 주어진다.

세 번째 줄에는 $A_{2,1}, A_{2, 2}, \cdots A_{2, N}$가 공백으로 구분되어 주어진다.

출력

최선을 다해 게임을 했을 때, 오토와 데이브가 가져가는 물고기의 마릿수를 공백으로 구분하여 출력한다.

제한

• 2ドル \leq N \leq 500,000円$
• $A_{1,1} = A_{2,N} = 0$
• $(i, j) \neq (1, 1), (2, N)$일 때, 1ドル \leq A_{i,j} \leq 1,000円,000円$
• 주어지는 모든 수는 정수이다.

힌트