思路：动态规划

考虑动态规划，定义$dp[i][j][0/1]$表示移动到了$(i,j)$且第$0/1$个人操作完后的成本，$Min$即代表最小成本，$Max$即代表最大成本。

当从终点向起点求解时，就有向上/下、向左三种方法，根据不同的方法更新$dpMin,dpMax$数组即可。

题目内容

给定一个$2$行$N$列的矩阵$A$。一个有效路径为从起点($1,1$)出发，经过向上、向下或向右的移动，不重复访问同一个方格，最终到达终点($2,N$)。

现在有两名玩家，他们轮流选择路径上的下一个方格(游戏从第一个玩家选择方格($1,1$)开始)。当路径到达终点($2,N$)时，游戏停止。

路径的成本定义为路径上所有方格上数字的总和。第一个玩家希望最大化路径的成本，而第二个玩家希望最小化路径的成本。如果两个玩家都采取最优策略，路径的成本将是多少？

输入描述

第一行输入一个整数 $N$（$1≤N≤10^5$）表示矩阵的列数。

接下来两行，每行均包含$N$个整数，表示矩阵$A$中的元素($-10^5≤A_{ij}≤10^5$)。

输出描述

输出一个整数，表示两个玩家都采取最优策略下的路径成本。

样例1

输入

3 
1 5 2
3 4 0

输出

8

说明

两个玩家都采取最优策略下的路径为：$1\rightarrow3\rightarrow4\rightarrow0$，路径成本为$1+3+4+0=8$