Имеются 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.

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

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