Problems
Преобразование массивов
Преобразование массивов
У нас есть массив положительных чисел. Мы должны преобразовать этот массив повторяя одну и ту же операцию, пока не останется менее двух элементов в массиве:
\begin{enumerate}
\item выбрать два элемента, которые имеют минимальную абсолютную разницу. Если таких пар несколько, то выбрать пару, чья сумма элементов минимальна. Если все равно осталось несколько пар, то выбрать любую.
\item уменьшить значение элементов выбранной пары на \textbf{1}.
\item удалить нулевые элементы массива.
\end{enumerate}
Легко заметить, что процесс конечен за фиксированное количество шагов.
Например, имеем массив из \textbf{4} элементов \{\textbf{3}, \textbf{2}, \textbf{3}, \textbf{2}\}. Процесс преобразования будет происходить следующим образом:
\begin{itemize}
\item Step \textbf{1}: \{\textbf{3}, \textbf{2}, \textbf{3}, \textbf{2}\} => \{\textbf{3}, \textbf{1}, \textbf{3}, \textbf{1}\} (уменьшаем элементы \textbf{2} и \textbf{2})
\item Step \textbf{2}: \{\textbf{3}, \textbf{1}, \textbf{3}, \textbf{1}\} => \{\textbf{3}, \textbf{3}\} (очередное уменьшение значений элементов делает их равными \textbf{0} и \textbf{0}, удаляем их)
\item Step \textbf{3}: \{\textbf{3}, \textbf{3}\} => \{\textbf{2}, \textbf{2}\}
\item Step \textbf{4}: \{\textbf{2}, \textbf{2}\} => \{\textbf{1}, \textbf{1}\}
\item Step \textbf{5}: \{\textbf{1}, \textbf{1}\} => \{ \}
\end{itemize}
Получили пустой массив. Необходимо узнать количество шагов преобразования.
\InputFile
В одной строке записана последовательность чисел разделенных между собой запятой и пробелом. После последнего числа стоит точка. Размер массива от \textbf{1} до \textbf{50}, каждый элемент может принимать значения от \textbf{1} до \textbf{1000}.
\OutputFile
Количество шагов преобразования данного массива.
Input example #1
3, 2, 3, 2.
Output example #1
5