题目描述

给定一个长度为n的序列{a1, a2, ..., an}，求其最大上升子序列的和。注意：上升子序列定义为严格递增序列，即b1 < b2 < ... < bn。最长的上升子序列的和不一定是最大的。

输入格式

第一行，一个整数 n，表示序列长度。(n≤1000) 第二行有 n 个整数，表示这个序列。

输出格式

一行一个整数，表示所有上升子序列的和中的最大值。

样例

输入样例 1

7
1 7 3 5 9 4 8

输出样例 1

18

输入样例 2

3
1 2 3

输出样例 2

6

输入样例 3

3
3 2 1

输出样例 3

3