Vasya And The Mushrooms

题意翻译

Vasya 住在森林里,附近有一个会长蘑菇的空地。这个空地被分成两行,每行分为 $n$ 个连续的格子。Vasya 知道每分钟每个格子里能长多少个蘑菇。他要花一分钟从一个格子走到相邻的格子上,并且他不能离开空地。(我们称两个格子相邻,当且仅当它们有公共边。)当 Vasya 进入一个格子时,他会马上收集那个格子里的所有蘑菇。 Vasya 从左上角的格子开始收集蘑菇。因为他等不及蘑菇生长了,所以每分钟内他必须移动到一个相邻格子。他想每个格子都恰好走一遍并且最大化他所收集的蘑菇数量。一开始所有格子都没有蘑菇。Vasya也不一定要回到开始的格子。 帮帮 Vasya!计算出他能收集到的最大蘑菇数量。 ## 输入格式 第一行包含数字 $n(1 \le n \le 3 \cdot 10 ^ {5})$ —— 空地的长度。 第二行包含 $n$ 个数字 $a_ {1}, a_ {2}, \ldots, a_{n}$($1 \le a_{i} \le 10^{6}$) —— 在空地第一行的蘑菇的生长速度。 第三行包含 $n$ 个数字 $b_ {1}, b_ {2}, \ldots, b_{n}$($1 \le b_ {i} \le 10 ^ {6}$) —— 在空地第二行的蘑菇的生长速度。 ## 输出格式 输出一个数字—— Vasya 通过选择最佳路线可以收集的最大蘑菇总重量。 请注意,Vasya 必须将空地中的每个单元都访问一次。 ## 说明/提示 #### 样例1: 在第一个测试用例中,最佳路径如下: ![img](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1016C/fbb0db02f46ac40c8f18dc6a212852df14543f5e.png) 这样,蘑菇的收集重量将为 $0·1 + 1·2 + 2·3 + 3·4 + 4·5 + 5·6 =70$。 #### 样例2: 在第二个测试用例中,最佳路径如下: ![img](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1016C/0853812a60511dc1127814cc7d3f93535736820f.png) 这样,蘑菇的收集重量将为 $0·1 + 1·10 + 2·100 + 3·1000 + 4·10000 + 5·100000 =543210$

题目描述

Vasya'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.

输入输出格式

输入格式


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 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.

输入输出样例

输入样例 #1

3
1 2 3
6 5 4

输出样例 #1

70

输入样例 #2

3
1 1000 10000
10 100 100000

输出样例 #2

543210

说明

In the first test case, the optimal route is as follows: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1016C/fbb0db02f46ac40c8f18dc6a212852df14543f5e.png) Thus, the collected weight of mushrooms will be $ 0·1+1·2+2·3+3·4+4·5+5·6=70 $ .In the second test case, the optimal route is as follows: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1016C/0853812a60511dc1127814cc7d3f93535736820f.png) Thus, the collected weight of mushrooms will be $ 0·1+1·10+2·100+3·1000+4·10000+5·100000=543210 $ .