405383: GYM101931 F Торговый день

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

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

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

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

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

На вход подается число $$$1<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