В саду N деревьев разных видов и возраста расположены в один ряд. Раз в неделю необходимо поливать деревья. Для полива деревьев используются поливальные машины. Одна машина едет с левой стороны, другая – с правой. Когда машина подъезжает к дереву, она выливает необходимое количество воды. На выливание 1 литра воды требуется 1 минута, на переезд между соседними деревьями – 10 минут. Одно дерево может полить только одна машина. Количество воды, которым необходимо полить деревья, может отличаться, поэтому, если разместить воду в машины поровну, то вода в одной из машин может закончиться раньше и на полив всех деревьев уйдет больше времени.
Напишите программу, которая поможет определить, сколько литров воды нужно загрузить в каждую машину, чтобы полив завершился как можно быстрее.
Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке одно целое число N – количество деревьев (1 ≤ N ≤ 105). Каждая из следующих N строк содержит целое число в диапазоне от 0 до 104 – количество литров воды, которым требуется полить деревья слева направо.
Выходные данные
Два целых числа – количество литров воды, которые необходимо разместить в левой машине сначала для файла А, затем для файла В.
Пример организации исходных данных во входном файле:
5
3
1
8
3
4
Для указанных входных данных в левую машину необходимо поместить 12 литров, в правую 7. Тогда итоговое время полива левой машины будет равно 3 + 10 + 1 + 10 + 8 = 32, правой машины 4 + 10 + 3 + 10 = 27.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Файл А
Файл В