Bitonic Subsequence

A sequence of numbers (b_1, b_2, ..., b_m) is termed bitonic if there exists an index (j) ((1 < j < m)) such that the sequence satisfies the conditions (b_1 < b_2 < ...< b_j > b_j+1 > ...> b_m). According to this definition, a bitonic sequence must have at least three elements.

Consider a sequence of numbers (a_1, a_2, ..., a_n). A subsequence of this sequence is defined as:

(a_i_1, a_i_2, ..., a_i_k)

where the indices (i_1, ..., i_k) satisfy the condition (1 $\le$ i_1 $\le$ i_2 $\le$ ...$\le$ i_k $\le$ n).

Your task is to develop a program that identifies a bitonic subsequence from the given sequence such that the sum of the digits of the numbers in this subsequence is maximized. Assume that the numbers are represented in the decimal numeral system.

Input

The first line of the input contains an integer (n) ((3 $\le$ n $\le$ 1000)). The second line contains (n) integers (a_1, ..., a_n), which form the given sequence. Each integer satisfies the condition (1 $\le$ a_i $\le$ 10^9).

Output

On the first line of the output, print the maximum sum of the digits of the numbers in the identified bitonic subsequence. If no bitonic subsequence exists in the given sequence, output (-1).

Examples