Фермер Джон строит красивый сад, и в процессе стройки ему нужно убрать большое количество земли.

Сад состоит из последовательности 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.

Выход

Выведите минимальную общую стоимость, которую ФД должен потратить на благоустройство территории.