Олимпиадный тренинг

Задача 21996. Storage room from Prostokvashino


Задача

Темы:
Immediately after moving into a new house in Prostokvashino, the cat Matroskin, Sharik and Uncle Fyodor started repairs. Immediately before it began, they discovered that the house did not have a storage room for building materials, and hastily added it to the house. As soon as the auxiliary building was ready, the question arose of the need to conduct electricity there and hang a light bulb.

Having discussed the issues of electrification of new premises with the postman Pechkin, our heroes learned a lot of useful information. So that visitors do not suffer with the choice, the village shop sells only one type of light bulb, but in unlimited quantities. One light bulb costs neither expensive nor cheap, but exactly C rubles. True, the bulbs in the store are not of the highest quality, and each of them can be turned on only K times, and on K + 1 it burns out. This disadvantage is compensated by the fact that the light bulb cannot burn out when it is on. Unfortunately, electricity in Prostokvashino is not cheap, and every minute the light bulb works will cost Uncle Fyodor and his friends D rubles.

Having learned all this, the economical Matroskin made a per-minute schedule of N expected visits to the pantry. Each visit to a new room is given by an entry time ai and an exit time bi . Thus, the i-th visit continues exactly bi − ai minutes.

Of course, during the visit, the light in the closet must be turned on. If at the beginning of the next visit the light is off, then the visitor immediately turns it on, but when leaving, he can either turn off the light or leave it on. If during the next turn on the light bulb burns out, then it must be replaced immediately. Now Matroskin is interested in the minimum amount of rubles that will have to be spent in order to complete all the planned visits to the pantry. Initially, a new light bulb is already hanging in the room in the off state.

Input data format
The first line of the input contains four integers N, K, C, D — the number of planned visits to the pantry, the number of successful switching on for one bulb, the cost of buying a light bulb and the cost of a minute of light bulb operation, respectively (1 <= N, K <= 200,000, 1 <= C, D <= 109 ). The next N lines contain two positive integers ai and bi each, describing the expected visits to the pantry (1 <= ai < bi <= 10 9 ). The visits do not overlap in time and are ordered, i.e. bi < ai+1.

Output data format
Print a single integer — the minimum amount of rubles that the residents of the house will have to spend in order to complete all the planned visits to the pantry in the light.

Enter Output
1 2 5 6
3 5
12
3 1 15 10
1 3
4 5
30 35
105


Remark
Note In the first example, it is enough to pay only for electricity: the light bulb must be turned on in the third minute and turned off in the fifth, so the total costs are (5 − 3) × 6 = 12.
In the second example, it is advantageous not to turn off the light bulb between the first and second visitor, and for the third visitor to use a new light bulb