The Bovine Accordion and Banjo Orchestra

There are $2N$ cows ($3 \le N \le 1000$) forming an orchestra: $N$ accordionists and $N$ banjoists. Accordionist $i$ has a talent level $A_i$ and banjoist $j$ has a talent level $B_j$, where $0 \le A_i \le 1000$ and $0 \le B_j \le 1000$.

Farmer John pairs accordionists with banjoists to hold concerts. Pairing accordionist $i$ with banjoist $j$ earns exactly $A_i \cdot B_j$ dollars in donations.

The musicians are stubborn about their seating order, so the pairs must preserve the original order: if accordionist $i$ is paired with banjoist $j$, then no accordionist whose index is greater than $i$ may be paired with a banjoist whose index is less than $j$. Equivalently, if the chosen pairs are written in increasing order of accordionist index, their banjoist indices must be strictly increasing as well. As a result, some cows may have to be left unpaired.

Every unpaired cow is upset. Consider the accordionists on their own and break the unpaired ones into maximal groups of consecutive indices. A group whose talents sum to $S$ costs $S^2$ dollars (spent drowning their sorrows in orange soda). The same rule applies independently to the unpaired banjoists.

Formally, if accordionists $x$ through $y$ are all unpaired and form one maximal consecutive group, they cost $(A_x + A_{x+1} + \cdots + A_y)^2$ dollars, and the identical relationship holds for banjoists.

Farmer John foots this bill, so he accounts for it when choosing the pairings. Find the maximum net profit (total donations minus total soda cost) he can achieve.

• The first line contains a single integer $N$.
• The next $N$ lines contain $A_1, A_2, \ldots, A_N$, one value per line.
• The following $N$ lines contain $B_1, B_2, \ldots, B_N$, one value per line.

Print a single integer: the maximum net profit Farmer John can earn.

Worked example: suppose there are three accordionists with talents $1, 1, 5$ and three banjoists with talents $5, 1, 1$. The best plan pairs accordionist $3$ (talent $5$) with banjoist $1$ (talent $5$), earning $5 \times 5 = 25$ dollars. The two unpaired accordionists (talents $1$ and $1$) form one group costing $(1 + 1)^2 = 4$ dollars, and the two unpaired banjoists (talents $1$ and $1$) form another group costing $(1 + 1)^2 = 4$ dollars. The net profit is $25 - 4 - 4 = 17$.

Because pairing accordionist $i$ with banjoist $i$ for every $i$ is always a valid choice, the answer is never negative. The profits and costs can be large, so 64-bit integers are required.