27255번 - Призы 다국어

Миша участвует в процедуре награждения на интеллектуальном шоу. В процессе награждения ему последовательно предлагают призы. У каждого приза есть стоимость. Про каждый приз Миша должен заявить, хочет ли он его взять. После того, как Миша возьмет или пропустит приз, ему показывается следующий, и так далее, вернуться к предыдущим призам и изменить свое решение нельзя.

В качестве первого приза Миша может взять любой приз, а затем Миша может взять приз, если его стоимость строго больше стоимости предыдущего взятого им приза.

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

Первая строка ввода содержит целая число $n$ --- количество призов ($1 \le n \le 1000$). Вторая строка содержит $n$ чисел $a_1, a_2, \ldots, a_n$ --- стоимости призов в том порядке, в котором их покажут Мише ($1 \le a_i \le 10^9$).

Выведите одно число --- максимальную суммарную стоимость призов, которые может получить Миша.