Problem K: 数字匹配

Problem K: 数字匹配

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 141  Solved: 85
Submit Status Web Board

Creator:

Description

给出两个元素数量都为n的数组a和数组b。对于数组a中的每个元素,都必须找一个(而且最多一个)数组b中的元素进行匹配,数组b中的所有元素也都要被匹配到,也就是说一一匹配。匹配完成后,相互匹配的元素相乘,然后把所有的积相加。

例如:

数组a1 5 3

数组 b2 3 4

如果a中第一个元素跟b中第三个元素匹配,第二个元素跟b中第二个元素匹配,第三个元素跟b中第一个元素匹配,匹配完后相乘得到 1*45*33*2,求和得到结果1*4+5*3+3*2=25

如果a中第一个元素跟b中第二个元素匹配,第二个元素跟b中第三个元素匹配,第三个元素跟b中第一个元素匹配,匹配完后相乘得到 1*35*43*2,求和得到结果1*3+5*4+3*2=29


给出n和两个数组,分别计算求和的最大结果与最小结果。 


Input

第一行 一个数n,表示两个数组元素的个数 1<=n<=1000

第二行 n个数 表示数组a的各个元素ai0<ai<=1000 ai为正整数,(1<=i<=n)。

第三行 n个数 表示数组b的各个元素bi0<bi<=1000 bi为正整数,(1<=i<=n)。


Output

两个数 分别表示最大结果和最小结果。最大结果和最小结果可以相等。


Sample Input

3
1 5 3
2 3 4

Sample Output

31 23

SubmitStatus