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