Вдоль трассы с односторонним движением расположены 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
Название |
---|