Олимпиадный тренинг

Задача . E. Транспортировка товаров


Задача

Темы: дп жадные алгоритмы Потоки *2900

Вдоль трассы с односторонним движением расположены 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) — количество единиц товара, которое может быть продано в каждом городе.

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

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


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

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет