← 返回题目列表

Codeforces · 1016/C

C. 瓦夏和蘑菇

中文机器翻译题面 查看原题

Vasya的房子坐落在森林里,附近有一片蘑菇空地。林间空地由两行组成,每一行都可以分为 n 个连续的单元格。对于每个单元,Vasya 知道该单元中蘑菇生长的速度(更正式地说,该单元中每分钟生长多少克蘑菇)。 Vasya 恰好花了一分钟时间移动到某个相邻的单元格。瓦夏无法离开这片空地。如果两个单元格共享公共边,则它们被视为相邻。当瓦夏进入某个牢房时,他立即收集了那里生长的所有蘑菇。

Vasya 在左上牢房开始他的旅程。瓦斯亚必须移动到相邻的牢房的每一分钟,他就迫不及待地等待蘑菇生长。他希望对所有单元格进行一次访问,并最大化收集到的蘑菇的总重量。最初,所有蘑菇的权重均为 0。请注意,Vasya 不需要返回起始单元格。

帮助瓦夏!计算他可以采集的蘑菇的最大总重量。

输入

第一行包含数字 n (1 ≤ n ≤ 3·105) — 林间空地的长度。

第二行包含 n 个数字 a1, a2, ..., an (1 ≤ ai ≤ 106) — 空地第一行蘑菇的生长速度。

第三行包含 n 个数字 b1, b2, ..., bn (1 ≤ bi ≤ 106) 是空地第二行蘑菇的生长速度。

输出

输出一个数字——Vasya通过选择最优路径可以采集到的蘑菇的最大总重量。请注意,瓦西娅必须访问林间空地的每个单元格一次。

示例

输入 #1

3
1 2 3
6 5 4

输出 #1

70

输入 #2

3
1 1000 10000
10 100 100000

输出 #2

543210

注意

第一个测试用例中,最优路线如下:

在第二个测试用例中,最优路线如下: