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

Успішно склавши сесію, Петрик збирається відправитись автівкою до своїх батьків у Кременчук, відстань до якого від університету рівна $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$.

Вихідні дані

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

Приклади

Примітка

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

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

Оцінювання

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

1. ($20$ балів): $n\le 16$;

2. ($20$ балів): $c_1=c_2=\cdots =c_n$;

3. ($20$ балів): $w=1$; $d\le 10^3$;

4. ($40$ балів): без додаткових обмежень.