33392번 - Simple Game 다국어

문제

Alice and Bob like playing games. Today they play on a special grid with 2ドル$ rows and $n$ columns. Alice and Bob each have a chess piece, starting at $(1,1)$ and $(2,n),ドル respectively. They will take turns moving their chess piece, with Alice going first.

In each turn, they can choose to stay still or move the chess piece to any point adjacent horizontally or vertically which has not been visited by the other's piece. The game will end after 10ドル^{10^{10}}$ turns.

Every point in this grid has a non-negative weight. For each player, the score that he/she gets is the sum of the weights of all the points his/her chess piece has visited. The weight is counted only once, even if the piece visited a point multiple times.

Both Alice and Bob want to maximize the score that they get. As a spectator, you want to know the score that Alice gets if both of them play optimally.

입력

The first line contains an integer $t,ドル the number of test cases (1ドル \le t \le 5 \cdot 10^4$). The test cases follow.

The first line of each test case contains a single integer $n$ representing the size of the grid (1ドル \le n \le 10^5$).

The second line of each test case contains $n$ integers $a_{1,1},a_{1,2},\ldots,a_{1,n}$. The $i$-th of them represents the weight of point $(1,i)$.

The third line of each test case contains $n$ integers $a_{2,1},a_{2,2},\ldots,a_{2,n}$. The $i$-th of them represents the weight of point $(2,i)$.

It is guaranteed that 0ドル \le a_{i,j} \le 10^9,ドル and the sum of $n$ across all test cases will not exceed 2ドル.5 \cdot 10^5$.

출력

For each test case, print a line with a single integer: the score that Alice gets if both players play optimally.

제한

힌트