Подорож на машині

У вас є $n$ міст, і ви плануєте подорож з міста $1$ до міста $n$ на автомобілі. Для цього вам потрібно придбати бензин. Відомо, що вартість одного літра бензину в $k$-му місті становить $cos{t}_k$. Спочатку ваш паливний бак порожній, і ви витрачаєте один літр бензину на кожен кілометр. Міста розташовані на одній прямій лінії в порядку зростання, причому $k$-те місто має координату $x_k$. Крім того, щоб в'їхати в $k$-те місто, потрібно сплатити в'їзне мито $tol{l}_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$.

Вихідні дані

Виведіть мінімально можливу вартість поїздки.

Приклади