E. Транспортировка товаров
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вдоль трассы с односторонним движением расположены n городов. Города пронумерованы числами от 1 до n в порядке проезда вдоль трассы.

В i-м городе было произведено pi единиц товара и может быть продано не более чем si единиц товара.

Для каждой пары городов i и j, таких что 1 ≤ i < j ≤ n, можно не более одного раза перевезти не более чем c единиц товара из города i в город j. Заметьте, что товар можно перевозить только из города с меньшим номером в город с большим номером. Перевозить товары между городами можно в любом порядке.

Определите, какое максимальное количество произведённого товара суммарно может быть продано во всех городах после некоторой последовательности перевозок.

Входные данные

Первая строка входных данных содержит два числа n и c (1 ≤ n ≤ 10 000, 0 ≤ c ≤ 109)  — количество городов и максимальное количество товаров, которое можно перевезти между городами за один раз.

Во второй строке записаны n чисел pi (0 ≤ pi ≤ 109) — количество единиц товара, произведённого в каждом городе.

В третьей строке записаны n чисел si (0 ≤ si ≤ 109) — количество единиц товара, которое может быть продано в каждом городе.

Выходные данные

Выведите одно число — максимальное количество товара, которое может быть продано во всех городах после некоторой последовательности перевозок.

Примеры
Входные данные
3 0
1 2 3
3 2 1
Выходные данные
4
Входные данные
5 1
7 4 2 1 0
1 2 3 4 5
Выходные данные
12
Входные данные
4 3
13 10 7 4
4 7 10 13
Выходные данные
34