Oz plays popular ARTS Dota 2. Invoker is one of the favourite Oz's heroes. Oz's skills are not perfect yet, so he uses only two spells - SunStrike and Tornado. Each of these spells takes some mana points to cast and may be used several times. Oz uses the spells to kill neutral creeps in the map. The creeps are placed at line OX, you may assume that each creep is a single point on the line. When Oz uses SunStrike, he kills all creeps placed on single point. When Tornado is used then it kills all creeps on a line segment (including creeps placed on the ends of the segment). Oz may cast spells in arbitrary order and may use them at any place of the line, however the length of Tornado segment is fixed. Help Oz to Find, what is the minimum amount of mana points he should spend to kill all the creeps.
Input : The first line contains three integers $M_s$, $M_t$ and $L_t$ - Number of mana points a single SunStrike takes, Number of mana points a single Tornado takes and length of Tornado segment. The second line contains a single integer $N$ - amount of creeps in the line. The next line contains $N$ non-negative integers $x_1, x_2,\ldots ,x_N$ - coordinates of creeps on the line.
Example
2 3 3
3
1 3 5
output
5
let us assume that all targets are on a line that is parallel to the in-game coordinate system, if there is any, so that we may avoid the necessity of pythagorean theorem. qute honestly,this question sems to be very simple, because the least common factor of the mana cost, when divided by the cost of the tornado spell is an intger, and th integer is 2. you see, with Tornado's mana cost being a, SunStrike's being b: ab/a will always be b and the value of b is 2. now, we multiply ab/a and a-b and get 2 since a-b is 1. Thereforefor a set of points upon every other point on he line or more compressed, you should use tornado, and if they are more spread you should use sunstrike to be the most efficient with your mana.