eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Путешествие на машине - 2

Путешествие на машине - 2

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Имеются n городов. Вы хотите поехать из города 1 в город n на машине. Для этого нужно купить бензин. Как известно, один литр бензина в k - ом городе стоит cost[k]. Изначально Ваш топливный бак пуст, и Вы расходуете один литр бензина на километр. Города расположены на одной линии в порядке возрастания, причем k - ый город имеет координату x[k]. Также необходимо заплатить toll[k], чтобы въехать в k - ый город. Ваша задача - совершить поездку с минимально возможной стоимостью.

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

Первая строка содержит количество городов n (1n10^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.

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

Выведите минимально возможную стоимость поездки.

Пример

Входные данные #1
5
1 4 5 8 10
6 8 2 4 6
7 2 5 4 7
Выходные данные #1
53
Автор Михаил Медведев