루미 알고리즘

#1465플래티넘Once in a Blue Moon

PO 2019 결선코딩출제 Lars Åström영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupPointsConstraints
115N, M, K ≤ 4, d_i,g_i,r_i ≤ 7
29N, K ≤ 300, d_i,g_i,r_i ≤ 1000
323N, K ≤ 300
428K=0
515g_i=i for every 1 ≤ i ≤ M
610No 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

출처 표기

출처: Programmeringsolympiaden 2019년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.