# Icons in the Toolbar

Gunnar is not satisfied with the graphic tools currently
available for L^{a}T_{e}X,
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.

100 |
99 |
98 |

3 |
1 |
2 |

## 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.

Sample Input 1 | Sample Output 1 |
---|---|

3 100 99 98 3 2 1 |
30591 |