Подорож на машині - 2
Існує n міст. Ви плануєте подорож з міста 1 до міста n на автомобілі. Для цього вам потрібно придбати бензин. Відомо, що один літр бензину в k-му місті коштує cost[k]. Спочатку ваш паливний бак порожній, і ви витрачаєте один літр бензину на кожен кілометр. Міста розташовані на одній прямій у порядку зростання, причому k-те місто має координату x[k]. Також потрібно сплатити toll[k], щоб в'їхати в k-те місто. Ваше завдання — здійснити поїздку з мінімально можливою вартістю.
Вхідні дані
Перша стрічка містить кількість міст n (1 ≤ n ≤ 10^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.
Вихідні дані
Виведіть мінімально можливу вартість поїздки.