#Pqjdp18. 4.生日欢唱

4.生日欢唱

4.生日欢唱

题目描述

生日演唱会采用一男一女合唱的形式,每个男生和女生都有一个演唱水平值,两个水平值分别为a和b的同学演唱将会给大家带来a*b的愉悦度。演唱会开始时,n名男生和n名女生各排成一列,我将会从两列的第一位同学开始,分别挑选一名男生和一名女生。如果觉得某位同学不适合登台,我就会请他回到座位,直到挑选到一位满意的同学为止。若最后有一位男生或女生找不到搭档,我只好请剩下的所有人(包括那名同学)回到座位。如果连续的一些女生或者男生没有登台演唱会损失她(他)们水平值之和的平方的愉悦度。请求出大家能获得最大的愉悦值。

输入格式

第一行包含一个整数n。

接下来n行,每行包含一个整数AiA_i,表示第i位男生的演唱水平值。

接下来n行,每行包含一个整数BiB_i,表示第i位女生的演唱水平值。

输出格式

输出一行,包含一个整数,即大家能获得最大的愉悦值。

数据范围

(原站未提供,导入后需人工补齐)

样例

3
1
1
5
5
1
1
17

提示

数据范围与提示

对于30%的数据,n<=50;

对于100%的数据,1<=n<=300,0<=Ai,Bi<=10001<=n<=300,0<=A_i,B_i<=1000。