Обход корпуса
Студент Андрей живёт в общежитии, и иногда случается такое, что в его комнате совсем кончается еда. И вот в один из таких голодных дней Андрей решил заглянуть к своим друзьям, дабы те с ним чем-нибудь поделились.
Общежитие Андрея устроено следующим образом: все комнаты пронумерованы целыми числами, причем последние три цифры этого числа есть номер комнаты на этаже, а оставшиеся первые цифры – номер этажа.
Например, номер 6007 означает, что данная комната находится на 6-м этаже и имеет номер 7, номер 16024 означает, что комната имеет номер 24 на 16-м этаже. Комнаты, имеющие одинаковые номера на этаже, но разные номера этажей находятся друг под другом. В общежитии имеется лестница. Лестница находится между p-й и (p+1)-й комнатой (p - номер комнаты на этаже). Как и многие студенты, Андрей немного ленив, поэтому он хочет, чтобы обход друзей отнял у него как можно меньше сил. Переход между i-й и (i+1)-й или (i-1)-й комнатами на одном этаже занимает 1 единицу силы. Переход между i-м и (i+1)-м или (i-1)-м этажами занимает, в зависимости от настроения Андрея, k единиц силы. Заход на лестничную площадку отнимает 0 единиц силы. Выход с площадки отнимает 1 единицу силы. Ваша задача состоит в том, чтобы помочь Андрею выбрать оптимальный (по затраченным силам) порядок обхода комнат. Естественно, Андрею необходимо вернуться в свою комнату, чтобы немедленно употребить добытое.
Для лучшего понимания условия см. примеры.
Иллюстрация к первому примеру (серым цветом обозначены лестничные площадки)
Иллюстрация ко второму примеру
Входные данные
Первая строка входного файла содержит четыре числа, разделенные пробелом: g, n, k, p (1 ≤ n < 10^6, 1 ≤ k < 1000), где g – номер комнаты, в которой живёт Андрей. Далее следуют n чисел, разделенных пробелом – номера комнат, в которых живут друзья Андрея. Все номера заданы в указанном выше формате. Гарантируется, что в корпусе менее 1000 этажей, а на этаже менее 1000 комнат. Этажи и комнаты нумеруются с 1. Переход между этажами не входит в межкомнатную нумерацию.
Выходные данные
Выходной файл содержит единственное число – минимальное количество сил, которые может потратить Андрей при обходе друзей.