Обміни з максимальною сумою#12951

Обміни з максимальною сумою

2 seconds
512 megabytes
Very hard

Вам задано масив a_1, a_2, \ldots, a_{2n} довжиною . За одну операцію можна вибрати довільний індекс з 1 \leq i \leq 2n-1 і поміняти місцями a_i, a_{i+1}.

Для кожного від до n^2 знайдіть найбільшу можливу суму a_1 + a_2 + \ldots + a_n, яку можна отримати після виконання не більше операцій.

Input

Перший рядок містить єдине ціле число .

Другий рядок містить цілих чисел a_1, a_2, \ldots, a_{2n} — елементи масиву.

1 \leq n \leq 100,

1 \leq a_i \leq 10^9.

Output

Виведіть n^2 + 1 ціле число: найбільшу можливу суму a_1 + a_2 + \ldots + a_n, яку можна отримати, виконавши не більше 0, 1, 2, \ldots, n^2 операцій.

Examples

Example

Loading
Loading

Note

Якщо не виконати жодної операції, сума a_1 + a_2 + a_3 = 1 + 2 + 3 = 6.

За одну операцію можна поміняти місцями a_3, a_4, отримавши a_1 + a_2 + a_3 = 1 + 2 + 4 = 7.