Обхід корпусу
Студент Андрій живе в гуртожитку, і час від часу в його кімнаті закінчується їжа. В один із таких днів він вирішив відвідати своїх друзів, щоб вони поділилися з ним чимось їстівним.
Гуртожиток, де живе Андрій, має таку структуру: всі кімнати пронумеровані цілими числами, де останні три цифри вказують на номер кімнати на поверсі, а решта цифр — на номер поверху.
Наприклад, номер 6007 означає, що кімната розташована на 6-му поверсі і має номер 7, а номер 16024 вказує на кімнату номер 24 на 16-му поверсі. Кімнати з однаковими номерами на поверсі, але різними номерами поверхів, розташовані одна під одною. У гуртожитку є сходи, які знаходяться між p-ю і (p+1)-ю кімнатами (p - номер кімнати на поверсі). Як і багато студентів, Андрій трохи лінивий, тому він хоче, щоб обхід друзів забрав у нього якомога менше сил. Перехід між i-ю і (i+1)-ю або (i-1)-ю кімнатами на одному поверсі займає 1 одиницю сили. Перехід між i-м і (i+1)-м або (i-1)-м поверхами займає, залежно від настрою Андрія, k одиниць сили. Захід на сходову площадку не потребує витрат сил, а вихід з неї забирає 1 одиницю сили. Ваше завдання — допомогти Андрію вибрати оптимальний маршрут обходу кімнат, щоб витратити якомога менше сил. Звісно, Андрію потрібно повернутися до своєї кімнати, щоб одразу ж насолодитися здобутим.
Для кращого розуміння умови дивіться приклади.
Ілюстрація до першого прикладу (сірим кольором позначені сходові площадки)
Ілюстрація до другого прикладу
Вхідні дані
Перший рядок вхідного файлу містить чотири числа, розділені пробілом: g, n, k, p (1 ≤ n < 10^6, 1 ≤ k < 1000), де g — номер кімнати, в якій живе Андрій. Далі йдуть n чисел, розділених пробілом — номери кімнат, в яких живуть друзі Андрія. Усі номери задані у вказаному вище форматі. Гарантується, що в корпусі менше 1000 поверхів, а на поверсі менше 1000 кімнат. Поверхи і кімнати нумеруються з 1. Перехід між поверхами не входить у міжкімнатну нумерацію.
Вихідні дані
Вихідний файл має містити єдине число — мінімальну кількість сил, які може витратити Андрій при обході друзів.