F. Торговый день
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Каждый день в Японии на рынок приплывают суда с уловом. Покупатели выбирают рыбу и просят мастеров разделать им ее на кусочки. Кусочек каждого размера имеет свою ценность и на него найдется свой покупатель.

Когда происходит разделка рыбы, перед мастером стоят покупатели, каждому из которых нужен кусочек определенного размера и он готов за это заплатить свою цену. При этом покупатель готов купить все получившиеся кусочки, которые его удовлетворяют.

Помогите мастеру максимально выгодно продать одну рыбу, зная ее размер.

Входные данные

На вход подается число $$$1 \lt N \leq 1000$$$ - размер рыбы.

Далее идут $$$N$$$ целых положительных чисел $$$p_i, i=1,\ldots,n$$$, которые задают сколько стоит кусок рыбы размера $$$i$$$.

Выходные данные

Единственное число, которое задает максимальную цену, за которую можно продать рыбу.

Примеры
Входные данные
4
1 5 8 9
Выходные данные
10
Входные данные
7
1 2 3 4 10 17 17
Выходные данные
18
Входные данные
6
10 11 13 15 21 3
Выходные данные
60
Входные данные
6
3 2 12 16 5 14
Выходные данные
24
Входные данные
6
1 2 5 8 13 14
Выходные данные
14