题目描述

给定长度为n的两个向量a和b,允许对向量的元素进行重排列,求排列完后向量a、b内积的最小值


输入格式

第一行为一个整数n,表示向量的长度
第二行为n个整数,表示向量a
第三行为n个整数,表示向量b


输出格式

一行一个整数,表示向量a、b内积的最小值


样例数据

输入

Input1:
3
5 3 2
3 4 5

Input2:
3
-5 3 -2
2 3 -2

输出

Output1:
37

Output2:
-25

备注

数据范围:
2<=n<=10^6
-10^9<=a[i]<=10^9
-10^9<=b[i]<=10^9
样例解释:
对于样例1,向量a(5,3,2),向量b(3,4,5),内积为5*3+3*4+2*5=37,可以证明此时为最小值
对于样例2,向量a为(-5,3,-2),向量b重排为(3,-2,2),内积为(-5)*3+3*(-2)+(-2)*2=-25,可以证明此时为最小值


操作

评测记录

优秀代码

信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

题解