Ландшафтный дизайн
Фермер Джон строит красивый сад, и в процессе стройки ему нужно убрать большое количество земли.
Сад состоит из последовательности n клумб, где клумба i изначально содержит a[i] единиц земли. Фермер Джон хотел бы изменить ландшафт сада, чтобы каждая клумба i вместо этого содержала b[i] единиц земли. a[i] и b[i] являются целыми числами в диапазоне 0 .. 10.
Чтобы благоустроить сад, у фермера Джона есть несколько вариантов: он может купить одну единицу земли и поместить ее на клумбу по своему выбору за x единиц денег. Он может удалить одну единицу земли с клумбы по своему выбору и выбросить ее за y единиц денег. Он также может переместить одну единицу земли с клумбы i на клумбу j за z * |i − j|. Подсчитайте минимальные общие затраты Фермера Джона на завершение его проекта по благоустройству.
Вход
Первая строка содержит n (1 ≤ n ≤ 10^5), x, y и z (0 ≤ x, y ≤ 10^8, 0 ≤ z ≤ 1000). Строка i + 1 содержит целые числа a[i] и b[i].
Выход
Выведите минимальную общую стоимость, которую ФД должен потратить на благоустройство территории.