Дорога в нове життя#11306

Дорога в нове життя

1 секунда

256 мегабайтів

Легка

Успішно склавши сесію, Петрик збирається відправитись автівкою до своїх батьків у Кременчук, відстань до якого від університету рівна $d$ кілометрів.

Машина Петрика не є новою, тому споживає цілих $w$ літрів бензину на кожен кілометр дороги. По дорозі до рідної домівки розміщено $n$ заправок, кожна з яких пропонує пальне за $c_{i}$ c_i гривень за літр та розміщена на відстані $x_{i}$ x_i кілометрів від точки відправлення. Проте, на подив, кожна заправка пропонує свій унікальний вид бензину, які змішувати між собою в баку не можна.

Перед поїздкою Петрик хоче замінити розмір бака для пального, проте не знає на який саме. Допоможіть Петрику визначити мінімальний розмір бака для пального такий, що вартість дороги до родичів буде мінімальною. Тобто першочергово слід мінімізувати затрати на пальне.

Гарантується, що початково бак пустий та існує таке $i$ , що $x_{i} = 0$ x_i = 0.

Вхідні дані

Перший рядок містить два цілі числа $d, w$ ( $1 \leq d, w \leq 1 0^{6}$ 1 \le d, w \le 10^6).

Другий рядок містить одне ціле число $n$ ( $1 \leq n \leq 1 0^{3}$ 1 \le n \le 10^3).

Третій рядок містить $n$ цілих чисел $c_{i}$ c_i ( $0 \leq c_{i} \leq 1 0^{6}$ 0 \le c_i \le 10^6).

Четвертий рядок містить $n$ цілих чисел $x_{i}$ x_i ( $0 \leq x_{i} \leq d$ 0 \le x_i \le d).

Гарантується, що існує таке $i$ , що $x_{i} = 0$ x_i = 0.

Вихідні дані

Виведіть мінімальний розмір бака для пального такий, що вартість дороги буде мінімальною.

Приклади

Приклад 1

Приклад 2

Примітка

У першому прикладі довжина дороги складає $10$ кілометрів, а витрати пального дорівнюють $10$ літрів на кілометр. Існує всього дві заправки: одна початкова з ціною $2$ гривні за літр та одна на відстані $4$ кілометри з ціною $1$ гривня за літр. Оскільки у другій заправці ціна найдешевша, то буде оптимально заправитись мінімально на першій заправці щоб доїхати до другої. Тоді на першій заправці слід заправити $4 \cdot 10 = 40$ 4 \cdot 10 = 40 літрів бензину, а на другій заправити необхідні для проїзду залишку дороги $6 \cdot 10 = 60$ 6 \cdot 10 = 60 літрів бензину. Таким чином мінімальний розмір баку щоб така дорога була можливою становить $60$ літрів.

У другому прикладі довжина дороги складає $10$ кілометрів, а витрати пального дорівнюють $5$ літрів на кілометр. Існує всього дві заправки: одна початкова з ціною $2$ гривні за літр та одна на відстані $2$ кілометри з ціною $4$ гривні за літр. Оскільки у першій заправці ціна найдешевша, то буде оптимально заправитись на ній до кінця дороги. Тоді на першій заправці слід заправити $5 \cdot 10 = 50$ 5 \cdot 10 = 50 літрів бензину, а на другій не заправлятись. Таким чином мінімальний розмір баку щоб така дорога була можливою становить $50$ літрів.

Оцінювання

У цій задачі застосовується потестове оцінювання. Якщо ваше рішення правильно працюватиме при таких обмеженнях, то гарантується, що воно отримає принаймні стільки балів:

1. ( $20$ балів): $n \leq 16$ n \leq 16; 2. ( $20$ балів): $c_{1} = c_{2} = \dots = c_{n}$ c_1 = c_2 = \dots = c_n; 3. ( $20$ балів): $w = 1$ w=1; $d \leq 1 0^{3}$ d \leq 10^3; 4. ( $40$ балів): без додаткових обмежень.