测试数据来自 system/1121

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　一个数的序列 \(b_i\)，当 \(b_1 < b_2 < … < b_S\) 的时候，我们称这个序列是上升的。对于给定的一个序列 \((a_1,a_2,…,a_N)\)，我们可以得到一些上升的子序列 \((a_{i_1},a_{i_2},…,a_{i_K})\)，这里 \(1<=i_1<i_2<…<i_K<=N\)。比如，对于序列 \((1,7,3,5,9,4,8)\)，有它的一些上升子序列，如 \((1,7), (3,4,8)\) 等等。这些子序列中序列和最大为 \(18\)，为子序列 \((1,3,5,9)\) 的和.
　　你的任务，就是对于给定的序列，求出最大上升子序列和。注意，最长的上升子序列的和不一定是最大的，比如序列 \((100,1,2,3)\) 的最大上升子序列和为 \(100\)，而最长上升子序列为 \((1,2,3)\)。

【输入格式】

　　输入的第一行是序列的长度 \(N\)。第二行给出序列中的 \(N\) 个整数，这些整数的取值范围都在 0 到10000(可能重复)。

【输出格式】

　　最大上升子序列和.

【输入输出样例】

　Input

7
1 7 3 5 9 4 8

　Output

18

【数据限制】

　　\(1 <= N <= 1000\)

【来源】

　　Mr.he