eolymp
bolt
Try our new interface for solving problems
Problems

Запись CD

Запись CD

Time limit 1 second
Memory limit 64 MiB

На двух одинаковых приводах нужно записать K компакт-дисков. Время записи каждого из дисков задано в массиве A[1..K]. Найти минимальное время, необходимое для записи всех дисков, если каждый диск будет полностью записываться на каком-то одном приводе.

Input data

В первой строке число K, во второй - элементы массива A. Все числовые значения натуральные числа, не превышающие 100.

Output data

Ответ к задаче.

Examples

Input example #1
5
5 7 4 9 3
Output example #1
14