Background

水水题

Description

桌面上放着 $n$ 块磁铁，每块磁铁的两端各有一个数 $(l_i,r_i)$ ，你可以将一些磁铁拿走后将剩下的磁铁按原本的顺序衔接在一起。具体而言，将 $i,j (i < j)$ 两块磁铁衔接到一起会产生 $r_i \times l_j$ 的贡献。求最大贡献。

Format

Input

第一行一个数 $n$ ，接下来两行，每行 $n$ 个数，分别表示 $l_1,l_2,...,l_n$ 与 $r_1,r_2,...,r_n$

Output

一个数，表示最大贡献。

Samples

5
1 -1 3 -1 7
2 -1 1 5 8

40

Limitation

对于 $10 \%$ 的数据， $1 \le n \le 20$

对于 $30 \%$ 的数据， $1 \le n \le 5 \times 10^3$

对于 $100 \%$ 的数据， $1 \le n,|l_i|,|r_i| \le 5 \times 10^5$