Студент Андрей живёт в общежитии, и иногда случается такое, что в его комнате совсем кончается еда. И вот в один из таких голодных дней Андрей решил заглянуть к своим друзьям, дабы те с ним чем-нибудь поделились. Общежитие Андрея устроено следующим образом: все комнаты пронумерованы целыми числами, причем последние три цифры этого числа есть номер комнаты на этаже, а оставшиеся первые цифры -- номер этажа. Например, номер \textbf{6007} означает, что данная комната находится на \textbf{6}-м этаже и имеет номер \textbf{7}, номер \textbf{16024 }означает, что комната имеет номер \textbf{24} на \textbf{16}-м этаже. Комнаты, имеющие одинаковые номера на этаже, но разные номера этажей находятся друг под другом. В общежитии имеется лестница. Лестница находится между \textbf{p}-й и \textbf{(p+1)}-й комнатой (\textbf{p} - номер комнаты на этаже). Как и многие студенты, Андрей немного ленив, поэтому он хочет, чтобы обход друзей отнял у него как можно меньше сил. Переход между \textbf{i}-й и \textbf{(i+1)}-й или \textbf{(i-1)}-й комнатами на одном этаже занимает \textbf{1} единицу силы. Переход между \textbf{i}-м и \textbf{(i+1)}-м или \textbf{(i-1)}-м этажами занимает, в зависимости от настроения Андрея, \textbf{k} единиц силы. Заход на лестничную площадку отнимает 0 единиц силы. Выход с площадки отнимает \textbf{1} единицу силы. Ваша задача состоит в том, чтобы помочь Андрею выбрать оптимальный (по затраченным силам) порядок обхода комнат. Естественно, Андрею необходимо вернуться в свою комнату, чтобы немедленно употребить добытое. Для лучшего понимания условия см. примеры. \includegraphics{https://static.e-olymp.com/content/48/48870a959d2c24d229d2b211948d41ade6f972bd.jpg} Иллюстрация к первому примеру (серым цветом обозначены лестничные площадки) \includegraphics{https://static.e-olymp.com/content/ef/ef4d9a9c472aaf2932c7133f4bd95694cd1fde2c.jpg} Иллюстрация ко второму примеру \InputFile Первая строка входного файла содержит четыре числа, разделенные пробелом: \textbf{g}, \textbf{n}, \textbf{k}, \textbf{p} (\textbf{1} ≤ \textbf{n} < \textbf{10^6}, \textbf{1} ≤ \textbf{k} < \textbf{1000}), где \textbf{g} -- номер комнаты, в которой живёт Андрей. Далее следуют \textbf{n} чисел, разделенных пробелом -- номера комнат, в которых живут друзья Андрея. Все номера заданы в указанном выше формате. Гарантируется, что в корпусе менее \textbf{1000} этажей, а на этаже менее \textbf{1000} комнат. Этажи и комнаты нумеруются с \textbf{1}. Переход между этажами не входит в межкомнатную нумерацию. \OutputFile Выходной файл содержит единственное число -- минимальное количество сил, которые может потратить Андрей при обходе друзей.