SP2189 MKPAIRS - Making Pairs

在一个手风琴和班卓琴乐团中，共有 $2 \times N$（$3 \leq N \leq 1,000$）头奶牛。每头奶牛演奏乐器的水平各不相同：第 $i$ 位手风琴手的才艺值是 $A_i$（$0 \leq A_i \leq 1,000$），第 $j$ 位班卓琴手的才艺值是 $B_j$（$0 \leq B_j \leq 1,000$）。 如果把才艺值分别为 $A_i$ 和 $B_j$ 的两头奶牛配成一组，他们的“精彩表现”直接取决于两头奶牛的才艺水平，这一组合将为农场主 FJ 带来 $A_i \times B_j$ 美元的“慈善捐款”。FJ 希望通过把奶牛以最盈利的方式结成对儿，来最大化他的总收入。 然而，手风琴手们有个小脾气，如果第 $i$ 号手风琴手与第 $j$ 号班卓琴手配对，那么从第 $i+1$ 位到第 $N$ 位的手风琴手就会拒绝和第 $1$ 到第 $j-1$ 位的班卓琴手配对。这些限制使得 FJ 必须在挑选队友时格外谨慎，因此有时需要忍痛让一些奶牛不参与配对。 况且，还有个问题，当音乐家们被要求不参与表演时，他们可能会可能因为怀才不遇而选择借酒消愁，随后要喝掉大量的冰镇橙色汽水——价值相当于他们浪费的才艺之和的平方。 具体而言，如果跳过了从第 $x$ 位到第 $y$ 位的手风琴手，他们将消耗价值 $(A_x + A_{x+1} + A_{x+2} + \ldots + A_y)^2$ 美元的橙色汽水。班卓琴手也遵循同样的规则。FJ 必须把奶牛的饮酒费用计入总账，因此这次他选择配对时尤其慎重。 请计算出，在收取捐款并支付汽水费用之后，FJ 可以赚取的最大总利润。

* 第 1 行：一个整数 $N$，代表每种乐器的奶牛数目。 * 第 2 到 $N+1$ 行：每行一个整数 $A_i$，表示第 $i$ 个手风琴手的才艺值。 * 第 $N+2$ 到 $2N+1$ 行：每行一个整数 $B_i$，表示第 $i$ 个班卓琴手的才艺值。

* 输出仅一行，一个整数，表示 FJ 最终可以获得的最大利润。 **本翻译由 AI 自动生成**