Задача №112122. Полетели!

Олимпиада завершена. Режим дорешивания.

Малыш и Карлсон решили отправиться погулять. А точнее, полетать. Карлсон, как любой ответственный человек, составил план полета и показал его Малышу. План полета выглядит следующим образом: для любого момента времени i Карлсон назначил высоту h i , на которой он в этот момент будет лететь.

Однако, из-за того, что совсем недавно они в очередной раз объелись варенья, Малышу не понравились перепады высот в плане Карлсона. Он решил чуть чуть подкорректировать план, чтобы полет проходил все время на одной высоте. Карлсон же, в свою очередь, заявил, что ему будет очень неприятно, если Малыш сильно изменит план полета. Более точно, если в i -ый момент времени Малыш изменит высоту в плане на один метр, то недовольство Карлсона увеличится на a i , где a i — показатель желания Карлсона пролететь в i -ый момент времени на выстоте, представленной в плане.

Таким образом, Малыш может изменить высоту в любой точке на любую величину, но из-за замены высоты в точке i на h i ± c i недовольство Карлсона увеличится на c i · a i . Помогите Малышу исправить план, заменив все высоты на какую-то одну, так, чтобы недовольство Карлсона при этом было минимально.

Входные данные

В первой строке входного файла задано одно число n ( 1 ≤ n ≤ 10 5 ) — длительность полета. Во второй строке задано n чисел h i ( 1 ≤ h i ≤ 10 6 ) — высота в i -ый момент времени. В третьей строке так же n чисел a i ( 1 ≤ a i ≤ 10 6 ) — коэфицент недовольства Карлсона в i -ый момент времени.

Выходные данные

Выведите два числа: конечную высоту полета и суммарное расстройство Карлсона. Если высот полета несколько, выведите минимальную.

Примечание

В случае, если вариантов ответа несколько, выведите лексикографически минимальную пару.

Оценивание:

  • Первая группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 1000 , h i ≤ 100 . Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 20 баллов.

  • Вторая группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 1000 . Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 40 баллов.

  • Третья группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 10 5 . Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 40 баллов.

Примеры
Входные данные
6
6 7 8 8 7 7
10 6 3 1 1 4
Выходные данные
7 14
Входные данные
5
7 5 7 9 8
10 8 7 8 5
Выходные данные
7 37
Входные данные
5
8 5 10 9 7
2 5 4 8 4
Выходные данные
9 34
Сдать: для сдачи задач необходимо войти в систему