Problem J
Icons in the Toolbar

Gunnar is not satisfied with the graphic tools currently available for L^aT_eX, so he’s working on his own graphics editor. For every editor function he has also created an icon which is a square image. These icons will be placed in a toolbar with two rows and $N$ columns. The height of a toolbar row is the same as the size of the biggest icon in the row. Similarly, the width of a column is the same as the size of the biggest icon in the column. The height of the toolbar is the sum of heights of all rows and the width of the toolbar is the sum of widths of all columns. Gunnar now wonders how he should order the icons so that the area of the toolbar is as small as possible.

Task

You will be given a sorted integer sequence $s_1, \ldots , s_{2N}$ denoting that the $i$-th icon has dimensions $s_ i\times s_ i$. Your task is to calculate the smallest possible area of a toolbar with 2 rows and $N$ columns.

Input

The first line of the input contains one integer $N, 1\leq N\leq 1\; 000\; 000$. Each of the next $2N$ lines contains one integer $s_ i$ denoting the size of an icon. You can assume that $1\; 000\; 000\geq s_{1}\geq s_2\geq \ldots \geq s_{2N}\geq 1$.

Output

The output consist of a single line with one integer – the smallest possible area of the toolbar.

3
100
99
98
3
2
1

30591