Последовательность чисел b₁, b₂, ..., b_m называется битонической, если существует такое число j (1< j < m), что выполняются неравенства b₁ < b₂ < ... < b_j > b_j+1 > ... > b_m. Заметим, что в соответствии с этим определением, битоническая последовательность должна содержать хотя бы три элемента.

   Пусть задана некоторая последовательность чисел a₁, a₂, ..., a_n. Ее подпоследовательностью называется последовательность следующего вида:

a_i1, a_i2, ..., a_ik

   При этом для чисел i₁, ..., i_k должны выполняться неравенства 1 ≤ i₁ ≤ i₂ ≤ ... ≤ i_k ≤ n.

   Ваша задача состоит в том, чтобы написать программу, которая найдет битоническую подпоследовательность заданной последовательности, для которой максимальна сумма цифр входящих в нее чисел. При этом предполагается, что числа записываются в десятичной системе счисления.

   Входные данные

   Первая строка входного файла содержит целое число n (3 ≤ n ≤ 1000). Вторая строка входного файла содержит n целых чисел a₁, ..., a_n - заданную последовательность. Для каждого из них верны неравенства 1 ≤ a_i ≤ 10⁹.

   Выходные данные

   В первой строке выходного файла выведите сумму цифр чисел, входящих в найденную битоническую подпоследовательность. Если у заданной последовательности нет битонических подпоследовательностей, выведите в выходной файл число -1.