#P5086. 「FJSC2018PJD8T2」最大上升子序列和

「FJSC2018PJD8T2」最大上升子序列和

Description

一个数的序列 bib_i,当 b1<b2<<bSb_1 < b_2 < \cdots < b_S 的时候,我们称这个序列是上升的。

对于给定的一个序列 (a1,a2,,aN)(a_1, a_2, \cdots, a_N),我们可以得到一些上升的子序列 ai1,ai2,,aiK)a_{i_1}, a_{i_2}, \cdots, a_{i_K}),其中 1i1<i2<<iKN1 \leq i1 < i_2 < \cdots < i_K \leq N

比如,对于序列 (1,7,3,5,9,4,8)( 1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如 (1,7)(1, 7), (3,4,8)(3, 4, 8)等等。 这些子序列中序列和最大为 1818,为子序列 (1,3,5,9)(1, 3, 5, 9)的和。

对于给定的序列,求出最大上升子序列和。注意,最长的上 升子序列的和不一定是最大的,比如序列 (100,1,2,3)(100, 1, 2, 3) 的最大上升子序列和为 100100,而最长上升子序列为 (1,2,3)(1, 2, 3)

Input Format

从文件seqsum.in读入

输入的第一行是序列的长度 NN

第二行给出序列中的 NN 个整数,这些整数的取值范围都在 001000010000(可能重复)。

Output Format

输出到seqsum.out,一个整数,为最大上升子序列和。

Sample

样例输入1 seqsum.in

7
1 7 3 5 9 4 8 

样例输出1 seqsum.out

18

Hint

(1N10001 \le N \le 1000)