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

Имеются $n$ городов. Вы хотите поехать из города $1$ в город $n$ на машине. Для этого нужно купить бензин. Как известно, один литр бензина в $k$ - ом городе стоит $cos{t}_k$. Изначально Ваш топливный бак пуст, и Вы расходуете один литр бензина на километр. Города расположены на одной линии в порядке возрастания, причем $k$ - ый город имеет координату $x_k$. Также необходимо заплатить $tol{l}_k$, чтобы въехать в $k$ - ый город. Ваша задача — совершить поездку с минимально возможной стоимостью.

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

Первая строка содержит количество городов $n(1\le n\le 1000)$.

Вторая строка содержит $n$ координат городов $x_1,...,x_n$. Координаты уникальны и отсортированы, $x_i<x_{i+1}$ для каждого $i=1,2,...,n-1$.

Третья строка содержит $n$ целых чисел — стоимости бензина $cos{t}_1,...,cos{t}_n$.

Четвертая строка содержит $n$ целых чисел — въездные пошлины $tol{l}_1,...,tol{l}_n$.

Известно, что координаты городов, стоимость бензина и въездные пошлины - неотрицательные целые числа, не превышающие $10^9$.

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

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

Примеры