Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Vasya And The Mushrooms

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVasya's house is situated in a forest, and there is a mushroom glade near it. The glade consists of two rows, each of which can be divided into *n* consecutive cells. For each cell Vasya knows how fast the mushrooms grow in this cell (more formally, how many grams of mushrooms grow in this cell each minute). Vasya spends exactly one minute to move to some adjacent cell. Vasya cannot leave the glade. Two cells are considered adjacent if they share a common side. When Vasya enters some cell, he instantly collects all the mushrooms growing there.

Vasya begins his journey in the left upper cell. Every minute Vasya must move to some adjacent cell, he cannot wait for the mushrooms to grow. He wants to visit all the cells exactly once and maximize the total weight of the collected mushrooms. Initially, all mushrooms have a weight of 0. Note that Vasya doesn't need to return to the starting cell.

Help Vasya! Calculate the maximum total weight of mushrooms he can collect.

Input

The first line contains the number *n* (1 ≤ *n* ≤ 3·10^{5}) — the length of the glade.

The second line contains *n* numbers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 10^{6}) — the growth rate of mushrooms in the first row of the glade.

The third line contains *n* numbers *b*_{1}, *b*_{2}, ..., *b*_{n} (1 ≤ *b*_{i} ≤ 10^{6}) is the growth rate of mushrooms in the second row of the glade.

Output

Output one number — the maximum total weight of mushrooms that Vasya can collect by choosing the optimal route. Pay attention that Vasya must visit every cell of the glade exactly once.

Examples

Input

3

1 2 3

6 5 4

Output

70

Input

3

1 1000 10000

10 100 100000

Output

543210

Note

In the first test case, the optimal route is as follows:

In the second test case, the optimal route is as follows:

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/15/2018 06:37:58 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|