시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

Nikola is a passionate collector of albums with images of football players. He and his friends compete with each other in a game they invented based on the albums whose images are currently being collected. The images in that album are divided into N teams, each of which has exactly M football players. The main rule of the game is that the total number of points a person wins for ith team is Bx, where x is the total number of unique pictures of football players of that team collected by the person. They have also agreed that the array B is growing, i.e. having more unique images of football players of a team means having more or equal points.

Nikola would like to win as many points as possible in the game. For each team x the amount of unique images Nikola currently owns of that team, Px, is known.

Ivan is a friend of Nikola who has already collected the entire album twice and when he heard about the game Nikola plays with his friends, he decided to give him any K images that Nikola wants. After finding out about this joyful news, Nikola wondered what is the maximal number of points he could have after Ivan gives him K images. Too excited for this news, he is not able to count and begs you to answer his question.

입력

In the first line there are integer numbers N, M and K (1 ≤ N, M ≤ 500, 1 ≤ K ≤ min(N·M, 500)), numbers from the task's text.

In the second line there is an array P consisting of N non-negative integer numbers (0 ≤ Pi ≤ M).

In the third line there is an array B consisting of M+1 non-negative integer numbers (0 ≤ Bi ≤ 100 000), amount of points Nikola gets for i (0 ≤ i ≤ M) unique images of a team.

For every t between 0 and M-1 it holds Bt ≤ Bt+1.

It is also holds that K ≤ N·M - (P1 + P2 + … + PN).

출력

In the only line print the answer to Nikola's question.

예제 입력 1

4 4 3
4 2 3 1
0 1 3 6 10

예제 출력 1

31

Nikola is most likely to ask Ivan to give him an image of the third team and two from the second, so that his score is 31 (10 + 10 + 10 + 1).

예제 입력 2

4 3 5
1 1 2 3
0 1 2 3

예제 출력 2

12

예제 입력 3

3 6 2
2 4 1
31 38 48 60 75 91 120

예제 출력 3

206