Подорож на машині#10776
У вас є міст, і ви плануєте подорож з міста до міста на автомобілі. Для цього вам потрібно придбати бензин. Відомо, що вартість одного літра бензину в -му місті становить cost_k. Спочатку ваш паливний бак порожній, і ви витрачаєте один літр бензину на кожен кілометр. Міста розташовані на одній прямій лінії в порядку зростання, причому -те місто має координату x_k. Крім того, щоб в'їхати в -те місто, потрібно сплатити в'їзне мито toll_k. Ваше завдання — здійснити подорож з мінімально можливою вартістю.
Перший рядок містить кількість міст n~(1 \le n \le 1000).
Другий рядок містить координат міст x_1, ..., x_n. Координати унікальні та відсортовані, x_i < x_{i+1} для кожного i = 1, 2, ..., n - 1.
Третій рядок містить цілих чисел — вартості бензину cost_1, ..., cost_n.
Четвертий рядок містить цілих чисел — в'їзні мита toll_1, ..., toll_n.
Відомо, що координати міст, вартість бензину та в'їзні мита — невід'ємні цілі числа, що не перевищують 10^9.
Виведіть мінімально можливу вартість поїздки.
Приклад 1