问题描述

一个数的序列 b~i~，当 b~1~ < b~2~ < ... < b~S~ 的时候，我们称这个序列是上升的。

对于给定的一个序列 (a~1~,a~2~,...,a~N~)，我们可以得到一些上升的子序列 (a~i1~,a~i2~,...,a~iK~)，这里满足 1 ≤ i~1~ < i~2~ < ... < i~K~ ≤ N。

例如，对于序列 (1,7,3,5,9,4,8)，它的上升子序列包括 (1,7)、(3,4,8) 等。其中和最大的子序列为 (1,3,5,9)，总和为 18。

你的任务是，对于给定的序列，求出最大上升子序列和。

注意：最长上升子序列的和不一定是最大的。例如序列 (100,1,2,3) 的最大上升子序列和为 100，而最长上升子序列为 (1,2,3)。

输入格式

• 第一行为序列的长度 N。
• 第二行给出 N 个整数（取值范围为 0 到 10000，可能重复）。

输出格式

输出一个整数，表示最大上升子序列和。

数据范围

1 ≤ N ≤ 1000

输入样例

7 1 7 3 5 9 4 8

输出样例

18