LISum

problem

Given the sequence $A$ of length $N$. Find the maximum value of $\ sum B_i$, where $B$ is one of the longest increasing subsequences of the sequence $A$.

The longest increasing subsequence of the sequence $A$ is the longest subsequence that satisfies $A_i <A_j$ with all $i <j$.

output

Output the maximum value of $\ sum B_i$, where $B$ is one of the longest increasing subsequences of the sequence $A$. Also, output a line break at the end.

Example

Input

4 6 4 7 8

Output

21

inputFormat

outputFormat

output

Output the maximum value of $\ sum B_i$, where $B$ is one of the longest increasing subsequences of the sequence $A$. Also, output a line break at the end.

Example

Input

4 6 4 7 8

Output

21

样例

4
6 4 7 8

21