Dangerous Delivery

F --Dangerous Delivery

Story

Person D had a serious mission. It is to deliver the next DAtaCoDer Regular Contest (DARC) D problem to Mr. Dhokudai, the president of DAtaCoDer. N cities are lined up in a straight line from city 1 where D's hideout is located to city N where the DAtaCoDer headquarters is located. During this move, a group of green triangles plotting injustice are aiming for the D problem, and they must protect the D problem from their devil's hands.

Fortunately, D's person has the ability to move across dimensional walls, so it's not easy to get caught. However, this movement method has some drawbacks. First of all, there is a gap when you start moving, and when you find that moment, you will find yourself at the destination. The green triangles continue to monitor each of them overlooking multiple cities. Moreover, reading the movement of the person in D, it seems that he is gradually moving in the direction of city N. Therefore, traveling from a city monitored by many green triangles or traveling a long distance increases the risk of discovery. The second drawback is that moving across a dimensional wall puts a strain on the body and can only be used once a day. It is also necessary to consider the pace distribution so that it will be in time for D days after the next DARC is held. It is unlikely that D's person will be captured like a green triangle, but the cautious D's person sought to minimize the risk of moving from City 1 to City N by D days later.

Problem

There are N cities on a two-dimensional plane. Cities 1 to N are aligned from left to right, and city i is in position (p_i, 0). Satisfy p_i <p_ {i + 1} (1 \ leq i <N).

In addition, there are M enemies on this two-dimensional plane, and the enemy j is initially in the position (a_j, b_j). Enemy j is watching the range of 45 ° up and down in the left direction. That is, all cities included in the area above the straight line y = x-a_j + b_j and below the straight line y = -x + a_j + b_j are in sight. Also, all enemies move to the right by exactly X every day. That is, the position of the enemy j on the dth day is (a_j + X (d-1), b_j).

Here, the degree of surveillance w_ {d, i} of the city i on the d day is defined by the total number of enemies who have the city i in sight on the d day. At this time, the movement from city i to city k on day d bears the risk of w_ {d, i} \ times | p_i-p_k |. If you can only move once a day, minimize the total risk of moving from city 1 to city N by D days later.

Input

The input consists of the following format.

N M D X p_1 p_2 ... p_N a_1 b_1 ... a_M b_M

The first line consists of four integers, and the number of cities N, the number of enemies M, the upper limit D of the number of days that can be moved, and the movement distance X of enemies per day are given, each separated by one blank character. The second line consists of N integers, and the i-th integer is given the x-coordinate p_i of the position of the city i, separated by a single character. The following M line is given the position information of the enemy. The second line of j + (1 \ leq j \ leq M) consists of two integers, and the x-coordinate a_j and y-coordinate b_j of the position of the enemy j on the first day are given by separating them with one blank character.

Constraints:

• 1 \ leq N \ leq 10 ^ 4
• 1 \ leq M \ leq 10 ^ 4
• 1 \ leq D \ leq 10 ^ 2
• 1 \ leq X \ leq 10 ^ 6
• 0 \ leq p_i, a_j \ leq 10 ^ 6, -10 ^ 6 \ leq b_j \ leq 10 ^ 6
• p_i <p_ {i + 1}

Output

Output the minimum sum of risks for being in city N by day D on one line. Be sure to start a new line at the end of the line.

Sample Input 1

3 2 2 1 0 3 6 1 1 3 -2

Sample Output 1

6

DangerousDelivery_sample1-1.png DangerousDelivery_sample1-2.png

On the first day, city 1 is monitored by 2 people, city 2 by 0 people, and city 3 by 0 people. Similarly, on the second day, city 1 is monitored by 2 people, city 2 by 0 people, and city 3 by 0 people. Therefore, on the first day, moving from city 1 to city 2 has a risk of 2 \ times | 3-0 | = 6, and on the second day, moving from city 2 to city 3 has a risk of 0 \ times | 6-3. The total of 6 of | = 0 is the minimum.

Sample Input 2

3 2 2 1 0 3 6 twenty one 3 -1

Sample Output 2

9

DangerousDelivery_sample2-1.png DangerousDelivery_sample2-2.png

The method of movement is the same as the first sample, but on the second day, the cost changes to 1 \ times | 6-3 | = 3 because the number of guards in city 2 increases by 1 due to the movement of the enemy. Therefore, the minimum risk is 9.

Sample Input 3

10 8 5 3 0 8 10 13 17 20 21 29 30 45 18 2 50 -20 17 1 38 21 40 -11 0 0 0 0 22 -1

Sample Output 3

222

Example

Input

3 2 2 1 0 3 6 1 1 3 -2

Output

6

inputFormat

Input

The input consists of the following format.

N M D X p_1 p_2 ... p_N a_1 b_1 ... a_M b_M

The first line consists of four integers, and the number of cities N, the number of enemies M, the upper limit D of the number of days that can be moved, and the movement distance X of enemies per day are given, each separated by one blank character. The second line consists of N integers, and the i-th integer is given the x-coordinate p_i of the position of the city i, separated by a single character. The following M line is given the position information of the enemy. The second line of j + (1 \ leq j \ leq M) consists of two integers, and the x-coordinate a_j and y-coordinate b_j of the position of the enemy j on the first day are given by separating them with one blank character.

Constraints:

• 1 \ leq N \ leq 10 ^ 4
• 1 \ leq M \ leq 10 ^ 4
• 1 \ leq D \ leq 10 ^ 2
• 1 \ leq X \ leq 10 ^ 6
• 0 \ leq p_i, a_j \ leq 10 ^ 6, -10 ^ 6 \ leq b_j \ leq 10 ^ 6
• p_i <p_ {i + 1}

outputFormat

Output

Output the minimum sum of risks for being in city N by day D on one line. Be sure to start a new line at the end of the line.

Sample Input 1

3 2 2 1 0 3 6 1 1 3 -2

Sample Output 1

6

DangerousDelivery_sample1-1.png DangerousDelivery_sample1-2.png

On the first day, city 1 is monitored by 2 people, city 2 by 0 people, and city 3 by 0 people. Similarly, on the second day, city 1 is monitored by 2 people, city 2 by 0 people, and city 3 by 0 people. Therefore, on the first day, moving from city 1 to city 2 has a risk of 2 \ times | 3-0 | = 6, and on the second day, moving from city 2 to city 3 has a risk of 0 \ times | 6-3. The total of 6 of | = 0 is the minimum.

Sample Input 2

3 2 2 1 0 3 6 twenty one 3 -1

Sample Output 2

9

DangerousDelivery_sample2-1.png DangerousDelivery_sample2-2.png

The method of movement is the same as the first sample, but on the second day, the cost changes to 1 \ times | 6-3 | = 3 because the number of guards in city 2 increases by 1 due to the movement of the enemy. Therefore, the minimum risk is 9.

Sample Input 3

10 8 5 3 0 8 10 13 17 20 21 29 30 45 18 2 50 -20 17 1 38 21 40 -11 0 0 0 0 22 -1

Sample Output 3

222

Example

Input

3 2 2 1 0 3 6 1 1 3 -2

Output

6

样例

3 2 2 1
0 3 6
1 1
3 -2

6