U135023 [AHOI2004] 实验基地 加强版

[P2545](https://www.luogu.com.cn/problem/P2545) 加强版，原题 $\mathcal O(n^2)$ 可过，这里来一个 $\mathcal O(n)$ 的。

给定一个 $2 \times n$ 的矩阵，第 $i$ 行第 $j$ 列的数为 $a_{i,j}$。 求一个凹形块使得凹形块里的数字和最大。 凹形块定义为一个 $2 \times w_1$ 的矩形，其中 $3 \le w_1 \le n$，然后在第一行把一块 $1 \times w_2$ 的矩形挖掉，其中 $1 \le w_2 \le n-2$，要保证挖掉之后第一行左右都有残留的部分。 如果本题面的凹形块描述不清可以去看原题面。

第一行一个整数 $n$ 代表矩阵大小。 接下来两行每行 $n$ 个整数 $a_{i,j}$ 代表这个矩阵。

一行一个整数代表选择的凹形块之和的最大值。

#### 数据规模与约定 对于 $20\%$ 的数据，$n \le 3000$。 对于 $100\%$ 的数据，$3 \le n \le 5 \times 10^6$，$|a_{i,j}| \le 1000$。 注：$20\%$ 的数据为原题数据规模。