Путешествие на машине - 2
Путешествие на машине - 2
Имеются n городов. Вы хотите поехать из города 1 в город n на машине. Для этого нужно купить бензин. Как известно, один литр бензина в k - ом городе стоит costk
. Изначально Ваш топливный бак пуст, и Вы расходуете один литр бензина на километр. Города расположены на одной линии в порядке возрастания, причем k - ый город имеет координату xk
. Также необходимо заплатить tollk
, чтобы въехать в k - ый город. Ваша задача - совершить поездку с минимально возможной стоимостью.
Входные данные
Первая строка содержит количество городов n (1 ≤ n ≤ 105
).
Вторая строка содержит n координат городов x1
, ..., xn
. Координаты уникальны и отсортированы, xi
< xi+1
для каждого i = 1, 2, ..., n - 1.
Третья строка содержит n целых чисел - стоимости бензина cost1
, ..., costn
.
Четвертая строка содержит n целых чисел - въездные пошлины toll1
, ..., tolln
.
Известно, что координаты городов, стоимость бензина и въездные пошлины - неотрицательные целые числа, не превышающие 109
.
Выходные данные
Выведите минимально возможную стоимость поездки.
5 1 4 5 8 10 6 8 2 4 6 7 2 5 4 7
53