Вдоль трассы с односторонним движением расположены 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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач