Problem A
Lång Bussresa

Resekudden runt halsen, hörlurarna på, och musiken på högsta volym. Nu är alla redo inför den långa bussresan ner till den underbara “Sunset Valley”!

Men oj! Alla på bussen verkar ha glömt att ta med sig vatten, och kommer att bli extremt törstiga under den långa bussresan. Men som tur är, så är det du som äger bussföretaget, och du har installerat en vattentunna som alla passangerare och chauffören kan dricka vatten ifrån. Tack vare tekniska framsteg kan vattentunnan hålla oändligt mycket vatten.

Bussen börjar att åka vid sekund $0$, och är framme vid Sunset Valley vid sekund $X$. Under resan finns det $N$ vattenstationer där man kan fylla bussens vattentunna med vatten. Bussen kommer att vara vid den $i$:te vattenstationen $(1 \leq i \leq N)$ vid sekund $S_ i$.

Från början finns inget vatten i vattentunnan. Som tur är finns åtminstone en vattenstation där bussen börjar åka ifrån. Kostnaden att fylla på vatten i vattentunnan är $W$ kr per liter, oavsett från vilken station man fyller på vatten från. Vi antar även att tiden det tar att fylla på vattentunnan är försumbar.

Från början sitter alla $M$ passagerare på bussen. Passagerarna är indexerade från $1$ till $M$. Den $j$:te passageraren $(1 \leq j \leq M)$ behöver $1$ liter vatten vid sekund $D_ j$. Om passageraren har druckit vatten, kommer den att behöva dricka vatten igen om $T$ sekunder. Alltså kommer passagerare $j$ behöva 1 liter vatten vid tiderna $D_ j + k\cdot T$ $(k = 0,1,2,\ldots )$. Notera att $T$ kommer vara samma för alla passagerare.

Om vattentunnan inte har vatten när en passagerare behöver vatten, så kommer passageraren att kräva att få gå av bussen. Om passageraren lämnar innan att den har kommit fram till Sunset Valley, så måste du återbetala deras bussbiljett som kostar $C_ j$ kr.

Chauffören behöver också dricka vatten, och kräver att få dricka vatten vid sekunderna $k\cdot T$ $(k = 0,1,2,\ldots )$. Om vattentunnan inte har vatten när chauffören vill ha vatten så slutar bussen köra och ingen kommer kunna åka till Sunset Valley.

Inga två passagerare kommer behöva vatten samtidigt. När bussen är framme vid en vattenstation, så kommer varken passagerare eller chauffören behöva vatten.

Genom att bestämma hur mycket vatten som fylls på i vattentunnan, vill vi minimera summan av kostnadenerna för vatten och återbetalningar, och samtidigt kunna köra till Sunset Valley. Kan du beräkna hur mycket pengar som du kan spendera som minst och ändå slutföra resan till Sunset Valley?

Indata

Den första raden innehåller heltalen $X$, $N$, $M$, $W$ och $T$ ($1 \leq T \leq X \leq 10^{12}, 1 \leq N,M \leq 2\cdot 10^5, 1 \leq W \leq 10^6$). Dessa innebär att bussen kommer att vara framme vid destinationen vid sekund $X$, att det finns $N$ vattenstationer, $M$ passagerare i bussen, kostnaden för vatten är $W$ kr per liter, och tidsintervallet för alla passagerare och chauffören att kräva vatten kommer att vara $T$ sekunder.

Därefter följer $N$ rader, där den $i$:te ($1 \leq i \leq N$) raden innehåller ett heltal $S_ i$ $(1 \leq S_ i \leq X-1)$, sekunden som bussen kommer att vara framme vid den $i$:te vattenstationen.

De kommande $M$ raderna innehåller heltalen $D_ j$ och $C_ j$ ($1 \leq D_ j \leq T-1$, $1 \leq C_ i \leq 10^9$), vilket representerar att den $j$:te passageraren kommer för första gången kräva vatten vid sekund $D_ j$, och kostnaden att återbetala $j$:te passagerarens biljett är $C_ j$.

Utdata

Skriv ut ett heltal: den minsta kostanden för att kunna köra bussen till Sunset Valley.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall 1:

Om vi fyller på 7 liter av vatten i vattentunnan innan vi börjar åka, och sedan 4 liter vid den första vattenstationen får vi följande händelser:

• Bussen börjar åka och har 7 liter vatten.

• Chauffören, passagerare 1,2,3,4 dricker 1 liter vatten var vid sekunderna 0,1,2,4 respektive 6. Nu har bussen endast 2 liter vatten kvar.

• Chauffören och passageraren 1 dricker 1 liter vatten var vid sekunderna 7 och 8. Nu finns det 0 liter vatten kvar.

• Vid sekund 9 vill passagerare 2 dricka vatten, men det finns inget vatten kvar. Därför lämnar passagerare 2.

• Vid sekund 10 fylls vattentunnan med 4 liter vatten, eftersom vi är vid den första vattenstationen. Nu finns 4 liter vatten i vattentunnan.

• Passagerarna 3, 4, chauffören och passagerare 1 dricker 1 liter var vid sekunderna 11, 13, 14, 15. Nu finns 0 liter vatten kvar.

• Vid sekund 18 vill passagerare 3 ha vatten, men det finns inget. Därför lämnar passagerare 3.

• Vid sekund 19 är bussen framme vid destinationen.

Totalt köptes 11 liter vatten, vilket kostar 88 kr. Endast passagerarna 2 och 3 lämnade och krävde återbetalning, vilket kostar 15 kr. Vi betalar totalt 103 kr.

Det är omöjligt att kunna ta sig till Sunset Valley för mindre än 103 kr.

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

103

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

547

1000000000000 1 1 1000000 6
999999259244
1 123456789

333333209997456789