장거리 버스

장거리 버스가 도시 I와 도시 O 사이를 달린다. 버스에는 물 공급기가 있어서 승객과 운전기사가 여기서 물을 마실 수 있다. 버스는 시각 $0$에 도시 I를 출발해 시각 $X$에 도시 O에 도착한다. 경로에는 $N$개의 급수 지점이 있고, 이곳에서 기계에 물을 넣을 수 있다. 버스는 $i$번째 급수 지점에 시각 $S_i$에 도착한다.

처음에 기계에는 물이 없다. 출발 전과 버스가 급수 지점에 있을 때 물을 넣을 수 있다. 물값은 버스의 위치와 관계없이 리터당 $W$엔이다.

도시 I에서 승객 $M$명이 탄다. 승객에게는 1번부터 $M$번까지 번호가 붙는다. 다른 곳에서는 승객이 타지 않는다. $j$번 승객은 시각 $D_j$에 물 1리터가 필요하다. 물을 마신 뒤에는 시간 $T$가 지나면 다시 1리터가 필요하다. 즉 $j$번 승객은 $D_j + kT$ ($k = 0, 1, 2, \ldots$) 시각에 물이 필요하다. 여기서 $1 \le D_j < T$이고, $T$는 모든 승객이 같다. 승객이 필요한 시각에 기계에 물이 없으면 그 승객은 버스에서 내린다. $j$번 승객이 도시 O에 도착하기 전에 내리면 운임을 환불해야 하며, 환불 비용은 $C_j$엔이다.

운전기사도 물이 필요하다. 운전기사는 승객과 같은 방식으로 시각 $kT$ ($k = 0, 1, 2, \ldots$)에 물이 필요하다. 운전기사가 필요한 시각에 기계에 물이 없으면 버스 운행이 멈춘다.

두 사람이 같은 시각에 물을 필요로 하지 않는다. 버스가 도시 O나 급수 지점에 도착한 시각에는 승객도 운전기사도 물이 필요하지 않다.

급수 지점에서 기계에 넣는 물의 양을 조절해, 버스가 도시 O까지 운행하면서 물값과 환불 비용의 합을 최소로 하라. 여행 중 어디에서 얼마만큼 물을 넣을지 정하라.

이동 시간, 급수 지점 시각, 승객과 운전기사 정보가 주어졌을 때, 버스가 도시 O에 도달한다고 가정하고 물값과 환불 비용의 합의 최솟값을 구하라.

첫 줄에 다섯 정수 $X$, $N$, $M$, $W$, $T$가 공백으로 구분되어 주어진다. 각각 도시 O 도착 시각, 급수 지점 수, 승객 수, 리터당 물값, 승객과 운전기사의 물 필요 간격 $T$이다.

다음 $N$개 줄에는 $i$번째 급수 지점에 버스가 도착하는 시각 $S_i$가 한 줄에 하나씩 주어진다.

다음 $M$개 줄에는 $D_j$와 $C_j$가 공백으로 구분되어 주어진다. $D_j$는 $j$번 승객이 처음 물을 필요로 하는 시각이고, $C_j$는 $j$번 승객의 환불 비용이다.

총 비용의 최솟값을 한 줄에 출력한다.

• $1 \le X \le 10^{12}$.
• $1 \le N \le 200\,000$.
• $1 \le M \le 200\,000$.
• $1 \le W \le 10^{6}$.
• $1 \le T \le X$.
• $1 \le S_i < X$ ($1 \le i \le N$).
• $1 \le D_j < T$ ($1 \le j \le M$).
• $1 \le C_j \le 10^{9}$ ($1 \le j \le M$).
• $D_j$ ($1 \le j \le M$)는 모두 서로 다르다.
• 버스가 도시 O나 급수 지점에 도착한 시각에는 승객도 운전기사도 물이 필요하지 않다.