Дети играют в следующую игру. На бесконечном разлинованном на клетки листе введена декартова система координат, при этом клетки таковы, что их вершины находятся во всех точках плоскости, для которых обе координаты целочисленные. Есть некоторое количество бумажных квадратов, стороны которых имеют целочисленные длины. Дети помещают на плоскость эти квадраты (возможно, не все) так, что нижние углы каждого квадрата лежат на оси абсцисс.
Входной файл содержит сведения о размерах квадратов. Квадраты необходимо размещать так, чтобы левый нижний угол самого первого квадрата находился в начале координат. Последующие квадраты размещаются таким образом, что абсцисса левого нижнего угла данного квадрата совпадает с абсциссой правого нижнего угла предыдущего, а длина квадрата меньше длины предыдущего на одну и ту же величину.
Входные данные
В первой строке входного файла находится число N (N ≤ 1000) – количество квадратов. Следующие N строк содержат числа, обозначающих длину стороны квадрата.
Запишите в ответе два числа: максимальное количество квадратов, которое могут разместить на плоскости дети, и какова при этом максимально возможная величина модуля разности абсцисс положений левых нижних углов первого и последнего квадратов, размещенных на плоскости.
Типовой пример организации данных во входном файле
7
1
2
4
7
8
10
11
При таких исходных данных можно взять максимум четыре квадрата, длины которых будут равны 10, 7, 4, 1 соответственно. Максимальная величина модуля разности абсцисс левых нижних углов первого и последнего квадратов в этом случае равна 21.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.