选择线段得到的最大价值

时间限制：2 s

空间限制：256 MB

题目描述

数轴上 $1,2,\cdots,n$ 处各有一个点，请选一条线段 $[l, r]$（需要满足 $1\le l\le r\le n$），使得线段的价值最大。

线段 $[l,r]$ 的价值 $v_{l,r}$ 按以下方法定义：

• 对于 $1\le i\le n$ 的每个整数 $i$：
  • 如果 $i$ 不在线段上，即不满足 $l\le i\le r$，线段 $[l,r]$ 的价值增加 $a_i$。
  • 如果 $i$ 在线段上，但不是端点，即 $l<i<r$，则线段 $[l, r]$ 的价值增加 $b_i$。
  • 如果 $i$ 在线段上，并且 $i$ 是线段的端点（即：$i=l$ 或 $i=r$ 成立），则线段 $[l, r]$ 的价值增加 $c_i$。

采用更正式的写法，即

$$v_{l,r}=\sum_{i=1}^{l-1}a_{i}+\sum_{i=r+1}^{n}a_i+\sum_{i=l+1}^{r-1}b_i+c_l+[l\neq r]\times c_r $$

其中，公式 $[l\neq r]$ 在 $l\neq r$ 时取 $1$，否则取 $0$。

请直接输出可取得的价值的最大值。

输入格式

第一行一个整数 $T$，表示测试数据组数。

接下来对于每一组测试数据：

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_i$。

第三行 $n$ 个整数 $b_i$。

第四行 $n$ 个整数 $c_i$。

输出格式

仅一个整数，表示选取线段能得到的最大价值。

样例输入1

3
5
100 10 100 100 20
10 20 30 30 50
40 150 10 200 10
5
1000 1000 1 1000 1000
1 1 1 1 1
1 1 1000 1 1
5
1000 1000 1000 1000 1000
1 1 1 1 1
1 1 1 1 1

样例输出1

500
5000
4001

样例 1 解释

对于第一组测试数据 选择 $[l, r]=[2, 4]$。第一个点的贡献是 $100$，第二个点的贡献是 $150$，第三个点的贡献是 $30$，第四个点的贡献是 $200$，第五个点的贡献是 $20$。

可以证明，没有价值更大的取法。

对于后两组测试数据，选择 $[l, r] = [3, 3]$

数据范围与约定

对于 $30\%$ 的数据，$1\le n\le 300$。

对于 $60\%$ 的数据，$1\le n\le 3000$。

对于另外 $20\%$ 的数据，$b_i=c_i$ 总是成立。

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

$1\le T\le 10^3$，所有测试点中 $n$ 的总和$\sum n\le 5\times 10^5$。

请注意，答案可能超出 $32$ 位整数可以表示的范围。