4.生日欢唱

题目描述

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

输入格式

第一行包含一个整数$n$。

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

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

输出格式

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

数据范围与提示

• 对于$30\%$的数据，$n < 50$；
• 对于$100\%$的数据，$1 < n < 300$，$0 \leq A_i,B_i \leq 1000$。

样例

3
1
1
5
5
1
1

17