월간 여행

Måna와 그녀의 자매 Solveig는 서로 멀리 떨어져 산다. 그래도 만나기 위해 Måna는 Solveig를 만나러 가는 날들을 예약했다. Måna가 Solveig에게 갈 수 있는 유일한 방법은 궤도를 타는 것이다. Solveig는 꽤 성급한 성격이라 Måna는 밤을 지내지 않고 같은 날 안에 다녀온다. 어차피 Måna는 저녁에 일로 바빠서 그게 낫다.

궤도를 타려면 당연히 돈이 든다. 원할 때 궤도를 탈 수 있는 게 자연법칙은 아니지 않은가. 여러 종류의 티켓이 있고, 각 티켓에는 유효 기간과 가격이 있다(예를 들어 월간권이 있을 수 있다). 더 긴 유효 기간은 항상 더 높은 가격을 뜻한다. Måna는 평소에 Marsbyrån에서 사는 편이지만, 가끔 출장을 가서 대신 Sevenus Elevenus를 방문할 수 있는데, 그곳에서는 모든 것이 Marsbyrån보다 절반 가격이다.

Måna는 $N$개의 서로 다른 날 $d\_1, \dots, d\_N$에 Solveig를 만나러 간다. $M$가지 티켓 종류가 있고, 티켓 종류 $i$는 유효 기간이 $g\_i$일이고 가격이 $p\_i$이다. 즉 $p\_i$는 Marsbyrån에서의 티켓 가격이다. 티켓은 온전한 하루 단위로만 유효하며 정확히 $g\_i$일 동안 유효하다. 이는 티켓 $i$를 $d$일에 사면 $d,d+1,\ldots,d+g\_i-1$일 동안 유효하다는 뜻이다. Måna는 $K$일 동안 출장 중인데, 그날들은 $r\_1 \dots r\_K$이다. 이 날들 중 하루에 산 티켓도 다른 티켓과 똑같이 즉시 효력이 시작된다. 티켓의 효력 시작일을 미룰 수는 없다. Måna가 궤도 티켓을 사도록 도와주고, 가능한 최소 가격이 얼마인지 알려주자!

입력은 다섯 줄로 이루어진다. 첫 번째 줄에는 세 정수가 주어진다.

• 방문 일수 $N$ ($1\leq N\leq 10^5$)
• 티켓 종류의 수 $M$ ($1\leq M\leq 10$)
• Måna가 출장 중인 날 수 $K$ ($0\leq K\leq 10^5$)

두 번째 줄에는 $N$개의 정수 $d\_i$ ($1 \leq d\_i \leq 5\cdot10^5$)가 주어지며, Måna가 Solveig를 방문하는 날들이다.

세 번째 줄에는 $M$개의 정수 $g\_i$ ($1 \leq g\_i \leq 5\cdot10^5$)가 주어지며, 각 티켓의 유효 기간이다.

네 번째 줄에는 $M$개의 정수 $p\_i$ ($2 \leq p\_i \leq 10^4$)가 주어지며, Marsbyrån에서의 각 티켓 가격이다. $p\_i$는 짝수임이 보장된다.

다섯 번째 줄에는 $K$개의 정수 $r\_i$ ($1 \leq r\_i \leq 5\cdot10^5$)가 주어지며, Måna가 출장 중이어서 절반 가격으로 티켓을 살 수 있는 날들이다.

마지막 네 줄의 수는 오름차순으로 주어지고, 한 줄에 있는 모든 수는 서로 다르다.

출력은 하나의 정수로, Måna가 Solveig를 방문하는 모든 날에 티켓을 가지기 위해 지불해야 하는 최소 금액이다. 출장 중인 날에는 티켓이 없어도 된다.

첫 번째 예제에서는 4일 동안 유효한 티켓을 $8$의 가격에 사는 것이 가장 싸다. 두 번째 예제에서는 1일권을 두 장 사서 총 $12$의 가격이 되는 것이 가장 싸다. 세 번째 예제에서는 4일권을 $7$의 가격에 사는 것이 가장 싸다(Måna가 1일째에 출장 중이므로). 네 번째 예제에서는 1일째에 1일권을 사고 5일째에 5일권을 사는 것이 가장 싸며, 총 가격은 $6$이다.