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