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 $i^{\text{th}}$ team is $B_x$, 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, $P_x$, 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.

Input

In the first line there are integer numbers $N$, $M$ and $K$ $(1\le N,M\le 500,1\le K\le min(N\cdot 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\le P_i\le M)$.

In the third line there is an array $B$ consisting of $M+1$ non-negative integer numbers $(0\le B_i\le 100000)$, amount of points Nikola gets for $i$ $(0\le i\le M)$ unique images of a team.

For every $t$ between $0$ and $M-1$ it holds $B_t\le B_{t+1}$.

It is also holds that $K\le N\cdot M-(P_1+P_2+\cdots +P_N)$.

Output

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

Scoring

In test samples totally worth 20% of the points it will hold $K=2$.

Sample Input 1

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

Sample Output 1

31

Explanation for Sample Output 1

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)$.

Sample Input 2

4 3 5
1 1 2 3
0 1 2 3

Sample Output 2

12

Sample Input 3

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

Sample Output 3

206