Problem D
Månresor

Måna och hennes syster Solveig bor långt ifrån varandra. För att de ska träffas ändå har nu Måna bokat in de dagar då hon ska åka till Solveig och hälsa på. Det enda sättet för Måna att ta sig till Solveig är genom att åka omloppsbanan. Solveig är ganska hetlevrad av sig så Måna stannar aldrig över natten utan åker fram och tillbaka under samma dag. Det är lika bra, för Måna är ändå upptagen med jobb kvällstid.

Att åka omloppsbana kostar såklart pengar – det är ju ingen naturlag att man ska få åka omloppsbana när man vill. Det finns några olika sorters biljetter, där varje biljett har en giltighetstid och ett pris (till exempel kanske det finns månadskort). En längre giltighetstid innebär alltid ett högre pris. Måna brukar handla på Marsbyrån i vanliga fall, men ibland är hon på jobbresor som gör att hon istället kan besöka Sevenus Elevenus, där allt kostar hälften så mycket som på Marsbyrån.

Måna ska hälsa på Solveig vid $N$ olika dagar, $d_1, \dots , d_ N$. Det finns $M$ olika biljettyper, där biljettyp $i$ har giltighetstid $g_ i$ dagar och pris $p_ i$. $p_ i$ är alltså priset för biljetten på Marsbyrån. Biljetterna gäller endast hela dygn och gäller i exakt $g_ i$ dygn. Det betyder att om biljett $i$ köps på dag $d$ är den giltig under dagarna $d,d+1,\ldots ,d+g_ i-1$. Måna är på jobbresa under $K$ dagar, nämligen dagarna $r_1 \dots r_ K$. Om en jobbresa inträffar på samma dag som Måna hälsar på Solveig så kan Måna köpa en billigare biljett och använda den under samma dag. Notera att en biljett köpt under någon av dessa dagar också börjar gälla på en gång, precis som de andra – man får aldrig skjuta upp dagen då en biljett ska börja gälla.

Hjälp Måna att köpa omloppsbanebiljetter och berätta vad det minsta möjliga priset är!

Indata

Inputen består av fem rader. Den första raden innehåller tre heltal:

• antalet besöksdagar $N$ ($1\leq N\leq 10^5$)

• antalet biljettyper $M$ ($1\leq M\leq 10$)

• och antalet dagar Måna är på jobbresa $K$, ($0\leq K\leq 10^5$).

Den andra raden innehåller $N$ heltal $d_ i$ ($1 \leq d_ i \leq 5\cdot 10^5$), dagarna då Måna ska besöka Solveig.

Den tredje raden innehåller $M$ heltal $g_ i$ ($1 \leq g_ i \leq 5\cdot 10^5$), giltighetstiderna för de olika biljetterna.

Den fjärde raden innehåller $M$ heltal $p_ i$ ($2 \leq p_ i \leq 10^4$), priserna för de olika biljetterna på Marsbyrån. Det garanteras att $p_ i$ är jämnt.

Den femte raden innehåller $K$ heltal $r_ i$ ($1 \leq r_ i \leq 5\cdot 10^5$), dagarna då Måna är på jobbresa och kan köpa biljetter för halva priset.

Talen på de fyra sista raderna ges i stigande ordning, och alla tal på en rad är olika.

Utdata

Utdata ska bestå av ett heltal, det minsta belopp som Måna måste betala så att hon har en biljett för alla resorna till Solveig. Hon behöver inte ha någon biljett under jobbresorna.

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. Nedan ser du en beskrivning av testfallsgrupperna.

Förklaring av exempelfall

I det första exemplet är det billigast att köpa en biljett som gäller fyra dagar till priset av $8$.

I det andra exemplet är det billigast att köpa två endagarsbiljetter, till priset av totalt $12$.

I det tredje exemplet är det billigast att köpa en fyradagarsbiljett till priset $7$ (eftersom Måna är på jobbresa dag $1$).

I det fjärde exemplet är det billigast att köpa en endagsbiljett dag $1$ och en femdagarsbiljett dag $5$ – vilket ger totalt pris $6$.

2 2 1
1 4
1 4
6 8
5

8

2 2 1
1 4
1 4
6 14
5

12

2 2 1
1 4
1 4
6 14
1

7

4 2 0
1 5 6 7
1 5
2 4

6