Optimal Musical Pairing

FJ is organizing a concert with his 2N cows, where N (3 ≤ N ≤ 1000) are accordion players and N are banjo players. Each accordion player has a talent score \(A_i\) and each banjo player has a talent score \(B_i\) (\(0 \le A_i, B_i \le 1000\)). When FJ pairs the \(i\)th accordion player with the \(j\)th banjo player, he gains a profit of \(A_i \times B_j\). However, there is a twist: if the \(i\)th accordion player is paired with the \(j\)th banjo player, then none of the accordion players \(i+1 \ldots N\) are allowed to pair with any banjo player from \(1 \ldots j-1\).

Furthermore, all unpaired ("depressed") cows will form consecutive groups and go to the bar. If a contiguous group of accordion players from \(x\) to \(y\) (with the property that the neighbor cows either do not exist or have been paired) remains unpaired, their cost is

[ \Bigl( \sum_{k=x}^{y} A_k \Bigr)^2. ]

A similar rule applies for banjo players.

FJ wishes to choose a pairing strategy (subject to the ordering constraint) to maximize his total revenue, which is the total profit from the chosen pairs minus the sum of the bar costs incurred by the unpaired cows. The penalty cost for a contiguous unpaired block in accordion (or banjo) players is the square of the sum of their talent scores.

Your task is to compute the maximum revenue FJ can achieve.

Note: In the input, the first number is N, followed by N integers for array A and N integers for array B.

inputFormat

The first line contains a single integer N (with 3 ≤ N ≤ 1000). The second line contains N space‐separated integers \(A_1, A_2, \ldots, A_N\) (\(0 \le A_i \le 1000\)), representing the talent scores of the accordion players. The third line contains N space‐separated integers \(B_1, B_2, \ldots, B_N\) (\(0 \le B_i \le 1000\)), representing the talent scores of the banjo players.

outputFormat

Output a single integer: the maximum revenue FJ can achieve with an optimal pairing strategy.

sample

3
1 2 3
3 2 1

7