Путешествие на машине - 2
Путешествие на машине - 2
Имеются n городов. Вы хотите поехать из города 1 в город n на машине. Для этого нужно купить бензин. Как известно, один литр бензина в k - ом городе стоит cost[k]
. Изначально Ваш топливный бак пуст, и Вы расходуете один литр бензина на километр. Города расположены на одной линии в порядке возрастания, причем k - ый город имеет координату x[k]
. Также необходимо заплатить toll[k]
, чтобы въехать в k - ый город. Ваша задача - совершить поездку с минимально возможной стоимостью.
Входные данные
Первая строка содержит количество городов n (1 ≤ n ≤ 10^5
).
Вторая строка содержит n координат городов x[1]
, ..., x[n]
. Координаты уникальны и отсортированы, x[i]
< x[i+1]
для каждого i = 1, 2, ..., n - 1.
Третья строка содержит n целых чисел - стоимости бензина cost[1]
, ..., cost[n]
.
Четвертая строка содержит n целых чисел - въездные пошлины toll[1]
, ..., toll[n]
.
Известно, что координаты городов, стоимость бензина и въездные пошлины - неотрицательные целые числа, не превышающие 10^9
.
Выходные данные
Выведите минимально возможную стоимость поездки.
Пример
5 1 4 5 8 10 6 8 2 4 6 7 2 5 4 7
53