[Usaco2007 China]The Bovine Accordion and Banjo Orchestra 音乐会

有两列按顺序排列的乐手： $N$ 名手风琴手和 $N$ 名班卓琴手。第 $i$ 名手风琴手的能力值为 $A_i$ ，第 $j$ 名班卓琴手的能力值为 $B_j$ 。

你可以选择一个整数 $k\ge 0$ ，以及两组下标序列：

i_1<i_2<\cdots<i_k,\qquad j_1<j_2<\cdots<j_k。

令第 $i_t$ 名手风琴手与第 $j_t$ 名班卓琴手组成第 $t$ 对进行演奏，这一对乐手会产生 $A_{i_t}\times B_{j_t}$ 的收益。

在每一列中，未参加演奏的乐手会按照原有顺序形成若干个极大连续段，每个极大连续段中的乐手组成一组去喝酒。若一组中所有乐手的能力值之和为 $S$ ，则该组会产生 $S^2$ 的费用。两列乐手的费用分别计算，参加演奏的乐手不会产生喝酒费用。当 $k=0$ 时，每一整列乐手均组成一个喝酒组。

总收益等于所有演奏组合产生的收益之和，减去所有喝酒组产生的费用之和。求总收益的最大值。

输入格式

第一行输入一个整数 $N$ 。

接下来 $N$ 行，第 $i$ 行输入一个整数 $A_i$ 。

再接下来 $N$ 行，第 $j$ 行输入一个整数 $B_j$ 。

输出一个整数，表示最大总收益。

让第 $3$ 名手风琴手与第 $1$ 名班卓琴手搭配，可以产生 $5\times 5=25$ 的收益。

第 $1$ 、 $2$ 名手风琴手组成一个喝酒组，产生 $(1+1)^2=4$ 的费用；第 $2$ 、 $3$ 名班卓琴手也组成一个喝酒组，产生 $(1+1)^2=4$ 的费用。

因此最终总收益为 $25-4-4=17$ 。

本题为 USACO 2007 China 试题「音乐会」，题面与测试数据整理自 BZOJ。