Бітонічна підпослідовність
Послідовність чисел b_1, b_2, ..., b_m називається бітонічною, якщо існує таке число j (1< j < m), що виконуються нерівності b_1 < b_2 < ... < b_j > b_{j+1} > ... > b_m. Відмітимо, що у відповідності з цим визначенням, бітонічна послідовність повинна містити хоча б три елементи.
Нехай задано деяку послідовність чисел a_1, a_2, ..., a_n. Її підпослідовністю називається послідовність наступного виду:
a_i1, a_i2, ..., a_ik
При цьому для чисел i_1, ..., i_k повинні виконуватись нерівності 1 ≤ i_1 ≤ i_2 ≤ ... ≤ i_k ≤ n.
Ваша задача полягає у тому, щоб написати програму, яка знайде бітонічну підпослідовність заданої послідовності, для якої максимальна сума цифр чисел, що входять до неї. При цьому припускається, що числа записано у десятковій системі числення.
Вхідні дані
Перший рядок вхідного файлу містить ціле число n (3 ≤ n ≤ 1000). Другий рядок вхідного файлу містить n цілих чисел a_1, ..., a_n - заданую послідовність. Для кожного з них вірні нерівності 1 ≤ a_i ≤ 10^9.
Вихідні дані
У перщому рядку вихідного файлу виведіть суму цифр чисел, що входять у знайдену бітонічну підпослідовність. Якщо у заданій послідовності немає бітонічних підпослідовностей, виведіть у вихідний файл число -1.