#Pqjdp18. 4.生日欢唱
4.生日欢唱
4.生日欢唱
题目描述
生日演唱会采用一男一女合唱的形式,每个男生和女生都有一个演唱水平值,两个水平值分别为a和b的同学演唱将会给大家带来a*b的愉悦度。演唱会开始时,n名男生和n名女生各排成一列,我将会从两列的第一位同学开始,分别挑选一名男生和一名女生。如果觉得某位同学不适合登台,我就会请他回到座位,直到挑选到一位满意的同学为止。若最后有一位男生或女生找不到搭档,我只好请剩下的所有人(包括那名同学)回到座位。如果连续的一些女生或者男生没有登台演唱会损失她(他)们水平值之和的平方的愉悦度。请求出大家能获得最大的愉悦值。
输入格式
第一行包含一个整数n。
接下来n行,每行包含一个整数,表示第i位男生的演唱水平值。
接下来n行,每行包含一个整数,表示第i位女生的演唱水平值。
输出格式
输出一行,包含一个整数,即大家能获得最大的愉悦值。
数据范围
(原站未提供,导入后需人工补齐)
样例
3
1
1
5
5
1
1
17
提示
数据范围与提示
对于30%的数据,n<=50;
对于100%的数据,。