该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给你两个长度都是 $n$ 的数组 $a_1\sim a_n$ 与 $b_1\sim b_n$。

现在允许你挑选 $b$ 中的连续一段来替换 $a$ 中的相应位置（也可以不选）。请问怎么选择可以使得替换后 $a_1\sim a_n$ 之和最大。请输出那个最大值。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个整数，$a_1\sim a_n$。

接下来一行 $n$ 个整数，$b_1\sim b_n$。

输出格式

一行一个整数，表示答案。

5
1 2 3 4 5
0 1 2 3 4

15

5
1 2 3 4 5
0 3 2 5 0

16

5
0 1 2 3 4
1 2 3 4 5

15

数据规模与约定

对于 $100\%$ 的数据，$1\le n \le 10^5$，$-10^9\le a_i,b_i\le 10^9$。

• 子任务 1（10 分）：保证 $n\le 1000$ 且 $b_i\ge a_i$
• 子任务 2（20 分）：保证 $n\le 1000$
• 子任务 3（70 分）：没有特殊限制