Description

A sequence of numbers b~i~ is called increasing if b~1~ < b~2~ < ... < b~S~. For a given sequence (a~1~, a~2~, ..., a~N~), we can obtain some increasing subsequences (a~i1~, a~i2~, ..., a~iK~), where 1 ≤ i~1~ < i~2~ < ... < i~K~ ≤ N. For example, for the sequence (1, 7, 3, 5, 9, 4, 8), some of its increasing subsequences are (1, 7), (3, 4, 8), etc. The maximum sum among these subsequences is 18, which comes from the subsequence (1, 3, 5, 9).

Your task is to find the maximum sum of an increasing subsequence for a given sequence. Note that the sum of the longest increasing subsequence is not necessarily the largest. For example, the sequence (100, 1, 2, 3) has a maximum increasing subsequence sum of 100, while the longest increasing subsequence is (1, 2, 3).

Input Format

The first line of input is the length of the sequence N (1 ≤ N ≤ 1000).
The second line contains N integers of the sequence, where the values of these integers range from 0 to 10000 (possibly with duplicates).

Output Format

The maximum sum of an increasing subsequence.

7
1 7 3 5 9 4 8

18