11184번 - Icons in the Toolbar 다국어

Gunnar is not satisfied with the graphic tools currently available for LATEX, 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.

Figure F.1: The height of this toolbar is 100 + 3 and the width 100 + 99 + 98. The total area is (100 + 3)·(100 + 99 + 98) = 30 591. This example corresponds to Sample Input 1.

You will be given a sorted integer sequence s₁, . . . , s_2N denoting that the i-th icon has dimensions s_i × s_i. Your task is to calculate the smallest possible area of a toolbar with 2 rows and N columns.

The first line of the input contains one integer N, 1 ≤ N ≤ 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 ≥ s₁ ≥ s₂ ≥ . . . ≥ s_2N ≥ 1.

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