Largest Sum Increasing Subsequence

You are given a sequence A. Find the increasing subsequence of A whose elements have the largest sum, and print that sum.

A subsequence is what you get by picking some elements of A and keeping their original order. An increasing subsequence is a subsequence whose picked elements grow strictly from left to right. For A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}, picking 1, 2, 50, 60 gives the sum 113, and no increasing subsequence of A has a larger sum.

The first line contains the size N of the sequence A. (1 ≤ N ≤ 1,000)

The second line contains the elements Ai of A, separated by spaces. (1 ≤ Ai ≤ 1,000)

Print on the first line the largest sum among the increasing subsequences of A.