题目内容

给定一个$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$