Campus
Student Andrey lives in campus, and sometimes it happens that he is out of food. So, one of this hungry days he decided to visit his friends to ask them for food.
Andrey's campus has the following structure: all rooms are numerated by integers. Three rightmost digits of the integer represent the number of the room on the floor, the remaining left digits - the floor.
For example, 6007 means that the room is located on the 6th floor, and has number 7. Number 16024 means that the room is located on the 16^th floor, and has number 24.
Rooms, that have similar numbers, but on different floors, are actually located one over another.
The campus has a staircase. Staircase is located between p-th and p+1-th rooms (p is the number of room on the floor). Andrey is very hungry, so he wants to spend minimal energy in his travel.
Move between neighbour rooms of the same floor takes 1 point of energy. Move between floors takes k point of energy (it depends on Andrey's mood). When Andrey enters staircase, he does not lose any point of energy, but when he leaves it, he loses 1 point.
Your task is to help Andrey choose optimal path to visit his friends, so that he loses minimal points of energy. Of course, Andrey must finally return to his room in order to eat taken food.
Look at examples to understand the problem better.
Illustration to the first example (marked in gray landings)
Illustration to the second example
Input
First line contains four numbers, separated with spaces: g, n, k, p (1 ≤ n < 10^6, 1 ≤ k < 1000), where g is the number of room where Andrey lives. Next line contains n numbers, separated by spaces - numbers of rooms where Andrey friends live. All numbers are given in the format mentioned in the statement. It is guaranteed that the campus has less than 1000 floors and each floor has less than 1000 rooms. Floors and rooms are numerated from 1. Movement between floors is not counted as movement between rooms.
Output
Output should contain the only number - minimal points of energy Andrey has to spend in his travel.