题目描述

给定一个 $2\times n$ 的长方形网格 $a$，请从中找出一片凸型的区域，使得这片区域的分数之和达到最大。

凸型区域定义为：

• 在第一行选择一个区间 $[l_1,r_1]$。
• 在第二行选择一个区间 $[l_2,r_2]$。
• 满足：$1\leq l_2<l_1\leq r_1<r_2\leq n$。

求出符合要求的凸型区域的数字之和的最大值。

输入格式

第一行一个数 $n$。

接下来两行每行 $n$ 个数。

输出格式

一行一个数表示答案。

10
8 9 -6 -8 3 -1 4 -3 10 -7
-4 -10 -5 1 5 6 -2 7 -9 2

23

样例 1 解释

最大的凸型区域如下所示：

5
1 1 1 1 1
-1 1 1 1 -1

4

提示

数据范围

本题采用捆绑测试。

对于 $100\%$ 的数据，$3 \le n \le 5 \times 10^5,0 \le |a_{i,j}| \le 10^9$。

• 子任务 1（$10$ 分）：$n\le 10$。
• 子任务 2（$20$ 分）：$n\leq 100$。
• 子任务 3（$30$ 分）：$n\leq 1000$。
• 子任务 3（$40$ 分）：无特殊限制。