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