Maximum Increasing Subsequence Sum

Problem Description

For a sequence $b_i$, when $b_1<b_2<\dots<b_s$, we call it increasing.

Given a sequence $(a_1,a_2,\dots,a_N)$, we can obtain some increasing subsequences $(a_{i1},a_{i2},\dots,a_{iK})$ where $1\le i_1<i_2<\dots<i_K\le N$. For example, from the sequence $(1,7,3,5,9,4,8)$ we get increasing subsequences such as $(1,7)$ and $(3,4,8)$. The largest sum among these is $18$, from the subsequence $(1,3,5,9)$.

Your task is, given a sequence, to compute the maximum increasing subsequence sum. Note that the longest increasing subsequence need not have the maximum sum; for example, the sequence $(100,1,2,3)$ has maximum increasing subsequence sum $100$, while its longest increasing subsequence is $(1,2,3)$.

Input Format

The first line is the length of the sequence $N\ (1\le N\le 1000)$.

The second line gives the $N$ integers of the sequence, each in the range $0$ to $10000$ (may repeat).

Output Format

The maximum increasing subsequence sum.

Sample Input

7
1 7 3 5 9 4 8

Sample Output

18