영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Luna and her brother Solomon live very far from each other. To make sure they still meet now and then Luna has already booked in a number of days in which she will go and visit Solomon. The only way for Luna to get to Solomon is by taking the Orbital. Since Solomon is pretty hot-tempered, Luna never stays during the night but goes there and home during the same day. It's probably for the best, since Luna works night shifts.
Taking the Orbital of course costs money – orbiting is not a natural law! There are different types of tickets for the Orbital, where each ticket has a certain time of validity and a price (for example there may be a moonthly ticket). A ticket with a longer time of validity is always more expensive than a ticket with a shorter time of validity. Usually, Luna shops at WHMars, but sometimes she travels because of work and can instead visit Sevenus Elevenus, where everything costs half as much as at WHMars.
Luna is visiting Solomon during N different days, d_1, …, d_N. There are M different types of tickets, where the i'th ticket is valid for g_i days and costs p_i. p_i is here the price of the ticket at WHMars. The tickets are only valid for an entire day and night and is valid for exactly g_i days and nights. This means that if ticket i is purchased during day d, it is valid during days d, d+1, …, d+g_i-1. If a work trip happens on the same day as a visit to Solomon, Luna is able to buy the cheaper ticket and use it during that day. Note that a ticket purchased during any of these days becomes valid immediately – you can never delay activating a ticket.
Help Luna to buy orbital tickets for all her visits to Solomon and tell her what the smallest possible price is!
Input
The input contains five lines. The first line contains three integers:
- the number of days N during which Luna visits Solomon (1 ≤ N ≤ 10^5)
- the number of types of tickets M (1 ≤ M ≤ 10)
- the number of days K during which Luna travels due to work (0 ≤ K ≤ 10^5).
The second line contains N integers d_i (1 ≤ d_i ≤ 5 · 10^5), the days during which Luna visits Solomon.
The third line contains M integers g_i (1 ≤ g_i ≤ 5 · 10^5), the times of validity for the various tickets.
The fourth line contains M integers p_i (2 ≤ p_i ≤ 10^4), the prices for the different types of the tickets at WHMars. p_i is always even.
The fifth and final line contains K integers r_i (1 ≤ r_i ≤ 5 · 10^5), the days during which Luna travels due to work and can buy tickets for half the price.
The numbers on the four last lines are given in strictly increasing order.
Output
Output should contain a single integer, the smallest amount Luna must pay so that she always has a valid ticket when she travels to Solomon.
She does not need any kind of ticket when she goes on a work trip.
Scoring
Your solution will be tested on a set of test case groups. To get the points for a group, you need to pass all the test cases in the group.
| Group | Points | Constraints |
| 1 | 15 | N, M, K ≤ 4, d_i,g_i,r_i ≤ 7 |
| 2 | 9 | N, K ≤ 300, d_i,g_i,r_i ≤ 1000 |
| 3 | 23 | N, K ≤ 300 |
| 4 | 28 | K=0 |
| 5 | 15 | g_i=i for every 1 ≤ i ≤ M |
| 6 | 10 | No further constraints |
Explanations of samples
In the first sample it's cheapest to buy a single ticket valid for 4 days at the price of 8.
In the second sample it's cheapest to buy two tickets vlaid a single day, at a total price of 12.
In the third sample it's cheapest to buy a single ticket valid for 4 days to the price of 7 (since Luna is on a work trip day 1).
In the fourth sample it's cheapest to buy a ticket valid one day at day 1 and a ticket valid five days at day 5 – for a total cost of 6.
예제
예제 1
2 2 1 1 4 1 4 6 8 5
8
예제 2
2 2 1 1 4 1 4 6 14 5
12
예제 3
2 2 1 1 4 1 4 6 14 1
7
예제 4
4 2 0 1 5 6 7 1 5 2 4
6