# Longest Increasing Subsequence with Maximum Sum

Given an array of n integers, you are asked to find the longest increasing subsequence of the array. If there are multiple such subsequences you can output any of them.
A subsequence of an array is obtained by deleting some (possibly zero) elements of the array, without changing the order of the remaining elements. For example, if the array is
, then
is a subsequence of
, but
is not a subsequence of
, since the order of the elements is not preserved.
π‘
An increasing subsequence of an array is a subsequence in which the elements are in increasing order. For example, if the array is
, then
is an increasing subsequence of
, but
is not an increasing subsequence of
, since the elements are not in increasing order.

#### Input

The first line of the input contains a single integer n (1 β€ n β€ 1000), the length of the array.
The second line contains n space-separated integers
(
), representing the elements of the array.

#### Output

The program should print the sum of the longest increasing subsequence with the maximum sum.
 Input Output 8 1 3 2 4 5 2 6 5 19 6 10 9 2 5 3 7 14

#### Explanation

1. In the first example, the longest increasing subsequence with maximum sum is
.
1. In the second example, the longest increasing subsequence with maximum sum is
.
Β

#### Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB