시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 256 MB13111090.909%

## 문제

There is a long-distance coach between the city I and the city O. It has a water supply machine. Passengers and the driver can drink water from it. The coach departs from the city I at time 0, and arrives the city O at time X. On the route, there are N refilling points where we can put water into the machine. The coach will arrive at the i-th refilling point (1 ≤ i ≤ N) at time Si.

In the beginning, the machine does not have water in it. We can put water into it before departure. Also, we can put water into it when the coach is at a refilling point. The cost of water is W yen per liter regardless of the position of the coach.

At the city I, M passengers get on the coach. The passengers are numbered from 1 to M. No passengers get on the coach at places other than the city I. The j-th passenger (1 ≤ j ≤ M) needs a liter of water at time Dj. If he drinks water, he will need a liter of water after a lapse of time T. In other words, the j-th passenger needs water at time Dj + kT (k = 0, 1, 2, . . .). Here, 1 ≤ Dj < T is satisfied, and the value of T is the same for all passengers. If the machine does not have water in it when a passenger needs water, the passenger leaves the coach. If the j-th passenger leaves the coach before getting to the city O, we need to refund the fare. The cost for refund is Cj yen.

The driver also needs water. If he drinks water, he will need a liter of water after a lapse of time T, just in the same way as passengers. In other words, the driver needs water at time kT (k = 0, 1, 2, . . .). If the machine does not have water in it when the driver needs water, the operation of the coach is stopped.

No two people will need water at the same time. When the coach arrives at the city O or a refilling point, neither passengers nor the driver need water.

Adjusting the amount of water put into machine at refilling points, we want to minimize the sum of the cost of water and the cost of refund, and to operate the coach until the city O. Your task is to decide where and how much we should put water into the water supply machine during the travel.

Given the traveling time for the coach, information on refilling points, and information on passengers and the driver, write a program which calculates the minimum of the sum of the cost of water and the cost of refund assuming the coach gets to the city O.

## 입력

Read the following data from the standard input.

• The first line of input contains five space separated integers X, N, M, W, T. This means the coach will arrive at the city O at time X, there are N refilling points, there are M passengers in the coach, the cost of water is W yen per liter, and the interval of time of water is T for passengers and the driver.
• The i-th line (1 ≤ i ≤ N) of the following N lines contains an integer Si. This means the coach will arrive at the i-th refilling point at time Si.
• The j-th line (1 ≤ j ≤ M) of the following M lines contains two space separated integers Dj ,Cj. This means the j-th passenger will need water at time Dj for the first time, and the cost for refund for the j-th passenger is Cj.

## 출력

Write one line to the standard output. The output contains an integer, the minimum total cost.

## 제한

• 1 ≤ X ≤ 1 000 000 000 000.
• 1 ≤ N ≤ 200 000.
• 1 ≤ M ≤ 200 000.
• 1 ≤ W ≤ 1 000 000.
• 1 ≤ T ≤ X.
• 1 ≤ Si < X (1 ≤ i ≤ N).
• 1 ≤ Dj < T (1 ≤ j ≤ M).
• 1 ≤ Cj ≤ 1 000 000 000 (1 ≤ j ≤ M).
• Dj (1 ≤ j ≤ M) are different from each other.
• When the coach arrives at the city O or a refilling point, neither passengers nor the driver need water.

## 서브태스크

번호 배점 제한
1 16

N ≤ 8, M ≤ 8.

2 30

N ≤ 100, M ≤ 100.

3 25

N ≤ 2 000, M ≤ 2 000.

4 29

## 예제 입력 1

19 1 4 8 7
10
1 20
2 10
4 5
6 5


## 예제 출력 1

103


In this sample input, if we put 7 liters of water into the machine before departure, and 4 liters of water into the machine at the first refilling point, the coach will be operated as follows:

1. The coach departs from the city I. At this time, the water supply machine has 7 liters of water.
2. The driver and the passengers 1, 2, 3, 4 drink 1 liter of water at time 0, 1, 2, 4, 6, respectively. The remaining amount of water is 2 liters.
3. The driver and the passenger 1 drink 1 liter of water at time 7, 8, respectively. The remaining amount of water is 0 liter.
4. At time 9, the passenger 2 needs water. But he leaves the coach because the machine does not have water in it.
5. At time 10, we put 4 liters of water into the machine at the first refilling point. The remaining amount of water is 4 liters.
6. The passengers 3, 4, the driver, and the passenger 1 drink 1 liter of water at time 11, 13, 14, 15, respectively. The remaining amount of water is 0 liter.
7. At time 18, the passenger 3 needs water. But he leaves the coach because the machine does not have water in it.
8. At time 19, the coach arrives at the city O.

Total amount of water used is 11 liters. The cost of water is 88 yen. The sum of the cost of refund for the passengers 2, 3 is 15 yen. The total sum is 103 yen.

We output 103 because it is impossible to operate the coach if the total cost is less than or equal to 102 yen,

## 예제 입력 2

105 3 5 9 10
59
68
71
4 71
6 32
7 29
3 62
2 35


## 예제 출력 2

547


## 예제 입력 3

1000000000000 1 1 1000000 6
999999259244
1 123456789


## 예제 출력 3

333333209997456789


## 채점 및 기타 정보

• 예제는 채점하지 않는다.