Наибольшая возрастающая подпоследовательность с максимальной суммой

Дан массив из n целых чисел. Ваша задача — найти самую длинную возрастающую подпоследовательность в этом массиве. Если таких подпоследовательностей несколько, можно вывести любую из них.

Подпоследовательность массива формируется путём удаления некоторых (возможно, ни одного) элементов без изменения порядка оставшихся. Например, если массив , то является подпоследовательностью массива , а — нет, потому что в ней не сохранён исходный порядок элементов.

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

В первой строке входных данных содержится одно целое число n (1 ≤ n ≤ 1000) — длина массива.

Во второй строке записаны n целых чисел (), которые являются элементами массива.

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

Программа должна вывести сумму самой длинной возрастающей подпоследовательности с максимальной суммой.

Пояснение

1. В первом примере самая длинная возрастающая подпоследовательность с максимальной суммой — это .

2. Во втором примере это подпоследовательность .