Степан збирається готувати \(N\) страв, які пронумеруємо від 1 до \(N\). Страву \(i\) можна приготувати за допомогою духовки за \(T_i\) хвилин. Духовку не можна використовувати для приготування двох або більше страв одночасно.

Якщо у Степана є дві духовки, який найменший час у хвилинах потрібен для приготування всіх \(N\) страв?

Припустимо, що всі процеси, крім використання духовок, займають незначний час.

Формат вхідних даних

Перший рядок містить ціле число \(N\) (\(1 \le N \le 100\))

Наступний  рядок містить \(N\) цілих чисел \(T_i\) (\(1 \le A_i \le 10^3\))

Формат вихідних даних

У вихідний потік виведіть шуканий час.

Примітка

До прикладу 1:

Наприклад, ми можемо використовувати дві духовки, щоб приготувати всі страви за 13 хвилин. Перша духовка:

• Готуйте страви 5 і 1 в такому порядку.

• Друга духовка: Готуйте страви 2, 4 і 3 у такому порядку.

Приклад вхідних даних

5
8 3 7 2 5

Приклад вихідних даних

13

Приклад вхідних даних

2
1000 1

Приклад вихідних даних

1000

Приклад вхідних даних

9
3 14 15 9 26 5 35 89 79

Приклад вихідних даних

138