Дорога в нове життя
ліміт часу на тест
1 second
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

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

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

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

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

Вхідні дані

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

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

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

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

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

Вихідні дані

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

Система оцінки

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

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

Приклади

Вхідні дані

    10 10
    2
    2 1
    0 4

Вихідні дані

    60

Вхідні дані

    10 5
    2
    2 4
    0 2

Вихідні дані

    50

Пояснення

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

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