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
注意
第一个测试用例中,最优路线如下:
在第二个测试用例中,最优路线如下: