第八集：魔法阵

"怎....怎么可能，我怎么可能会败...." 赛文斯在不甘的怒吼中慢慢消失……

突然！ 金光一闪！ "卧槽，出SS了！" 小A兴奋的说到，赶紧走近一看，却发现只是一条普通的环形珠子，每颗珠子上都有一个数字。

"切，我还以为气气之息呢！还是赶紧去找小C吧~"  ………………

"小C!!~~~~" "小A~~" 终于，小A来到的小C那儿，小A与小C一眼便看到了对方并朝着对方跑去~

只听"Duang~~"的一声，小A撞到了空气墙上，原来小C被魔法阵困住了，想要带她走，必须破了这个魔法阵！

"欲破此阵，必先自宫" 正在小A愁眉苦脸时，突然听到这样一句话，转头一看，却发现刚刚跑得没影的蛤蟆小晋正抖着腿一脸贱笑

"好啊，遇到危险你就跑没影了，现在安全了出来给我嘚瑟，让我给你安排得明明白白的！" 小A这次不容分说，上去就揍了小晋一顿

"别打了，别打了~~~打死了，你就救不出小C了，我知道怎么破这个魔法阵~~~"

"给你30秒时间，说得我不满意，你今天就交代在这里了" 小A恐吓到

"看到魔法阵外面石头没，上面刻着一圈数字bi，其实刚刚那串珠子是一把钥匙，每颗珠子都有一个数字ai，只要使得下面函数的值达到最大，魔法阵就会关闭"

"一句话，通过旋转珠子，使得Σai*bi最大，魔法阵就会消失！"

2019/5/1 update:数据增强，卡掉部分浮点数FFT

单组数据

开头是一个整数n，代表有n个数字。

第一行有n个整数代表a₀,a₁,a₂……a_n-1

第二行有n个整数代表b₀,b₁,b₂……b_n-1

n<=10⁵

0<=ai,bi<=10⁶

输出 f 函数的最大值

5
3 8 1 2 3
1 5 9 3 5

103
hint:
将a旋转至 3 3 8 1 2
此时f=3*1 + 3*5 + 8*9 + 1*3 + 2*5=103