Ландшафтный дизайн
Ландшафтный дизайн
Фермер Джон строит красивый сад, и в процессе стройки ему нужно убрать большое количество земли.
Сад состоит из последовательности n клумб, где клумба i изначально содержит ai
единиц земли. Фермер Джон хотел бы изменить ландшафт сада, чтобы каждая клумба i вместо этого содержала bi
единиц земли. ai
и bi
являются целыми числами в диапазоне 0 .. 10.
Чтобы благоустроить сад, у фермера Джона есть несколько вариантов: он может купить одну единицу земли и поместить ее на клумбу по своему выбору за x единиц денег. Он может удалить одну единицу земли с клумбы по своему выбору и выбросить ее за y единиц денег. Он также может переместить одну единицу земли с клумбы i на клумбу j за z * |i − j|. Подсчитайте минимальные общие затраты Фермера Джона на завершение его проекта по благоустройству.
Вход
Первая строка содержит n (1 ≤ n ≤ 105
), x, y и z (0 ≤ x, y ≤ 108
, 0 ≤ z ≤ 1000). Строка i + 1 содержит целые числа ai
и bi
.
Выход
Выведите минимальную общую стоимость, которую ФД должен потратить на благоустройство территории.
4 100 200 1 1 4 2 3 3 2 4 0
210