Задача №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