Giải bài trực tuyến

The 2*N (3 <= N <= 1,000) cows have assembled the Bovine Accordion and Banjo Orchestra! They possess various levels of skill on their respective instruments: accordionist i has an associated talent level A_i (0 <= A_i <= 1,000); banjoist j has an associated talent level B_j (0 <= B_j <= 1,000).

The combined A_i and B_j is directly proportional to the talents of each cow in the pair so a concert with those two cows will earn FJ precisely A_i * B_j dollars in "charitable donations". FJ wishes to maximize the sum of all revenue obtained by his cows by pairing them up in the most profitable way.

Unfortunately, FJ's accordionists are a bit stuck up and stubborn. If accordionist i is paired with banjoist j, then accordionists i+1..N refuse to be paired with banjoists 1..j-1. This creates restrictions on which pairs FJ can form. FJ thus realizes that in order to maximize his profits, he may have to leave some cows unpaired.

To make matters worse, when one or more of the musicians is skipped, they will be greatly upset at their wasted talent and will engage in massive binge drinking to wash away their sorrows.

After all pairings are made, a list is constructed of the groups of each of the consecutive skipped musicians (of either instrument). Every group of one or more consecutive skipped cows will gather together to consume kegs of ice cold orange soda in an amount proportional to the square of the sum of their wasted talent.

Specifically, FJ has calculated that if the x-th to y-th accordionists are skipped, they will consume precisely (A_x + A_x+1 + A_x+2 + ... + A_y)² dollars worth of orange soda in the process of drinking themselves into oblivion. An identical relationship holds for the banjoists. FJ realizes that he'll end up getting stuck with the bill for his cows' drinking, and thus takes this into account when choosing which pairings to make.

Find the maximum amount of total profit that FJ can earn after the contributions are collected and the orange soda is paid for.

Input

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains the single integer: A_i

* Lines N+2..2*N+1: Line i+N+1 contains the single integer: B_i

Output

* Line 1: A single integer that represents the maximum amount of cash that FJ can earn.

Example

Input:
3
1
1
5
5
1
1

Output:
17

Explanation

There are 6 cows: 3 accordionists and 3 banjoists. The accordionists have talent levels (1, 1, 5), and the banjoists have talent levels (5, 1, 1).

FJ pairs accordionist 3 with banjoist 1 to get earn A₃ * B₁ = 5 * 5 = 25 in profit. He loses a total of (1 + 1)² + (1 + 1)² = 8 dollars due to the cost of soda for his remaining cows. Thus his final (net) profit is 25 - 8 = 17.