题目描述

给你一个下标从0开始的二维数组grid，数组大小为2×n，其中grid[r][c]表示矩阵中(r,c)位置上的点数。现在有两个机器人正在矩阵上参与一场游戏。

两个机器人初始位置都是(0,0)，目标位置是(1,n-1)。每个机器人只会向右((r,c)到(r,c+1))或向下((r,c)到(r+1, c))。

游戏开始，第一个机器人从(0,0)移动到(1,n-1)，并收集路径上单元格的全部点数。对于路径上所有单元格(r,c)，途经后grid[r][c]会重置为0。然后，第二个机器人从(0,0)移动到(1,n-1)，同样收集路径上单元的全部点数。注意，它们的路径可能会存在相交的部分。

第一个机器人想要打击竞争对手，使第二个机器人收集到的点数最小化。与此相对，第二个机器人想要最大化自己收集到的点数。两个机器人都发挥出自己的最佳水平的前提下，计算第二个机器人收集到的点数 。

输入格式

第一行一个整数n(1≤n≤10^5)；

接下来2行，每行n个不大于10^5的整数。

输出格式

一个整数，表示第二个机器人收集到的点数。

输入/输出样例

3
3 3 1
8 5 2

4

4
1 3 1 15
1 3 3 1

7

样例1解释

第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示；

第一个机器人访问过的单元格将会重置为0；

第二个机器人将会收集到0+3+1+0=4 个点。

说明/提示

时间1000ms，内存256MiB