Problem Description

Nikola enjoys collecting photos of football players and storing them in albums. He plans to collect photos of players from $N$ teams, where each team has $M$ photos.

For each team Nikola collects, the number of photos $x$ from that team gives him a score of $B_x$. He currently has $P_i$ photos from team $i$.

Nikola's friend Ivan has two complete sets of albums. Ivan decides to give $K$ photos to Nikola. Nikola wants to know the maximum score his album can achieve after receiving these $K$ photos.

Input Format

The first line contains three integers $N$, $M$, and $K$.

The second line contains $N$ integers $P_i$.

The third line contains $M+1$ integers $B_i$, where $B_i$ represents the score obtained for collecting $i$ distinct photos from a team.

For each integer $t$ in the range $[0, M-1]$, $B_t \le B_{t+1}$. Additionally, $K \le N \times M - \sum_{i=1}^N P_i$.

Output Format

Output the maximum score that can be obtained.

Sample Input and Output

Sample Input #1

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

Sample Output #1

31

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

Notes

Sample 1 Explanation

Initially, Nikola has 4, 2, 3, and 1 photos from teams 1, 2, 3, and 4 respectively. The optimal strategy is to receive 1 photo each from teams 2 and 3. This maximizes the score to 10 + 10 + 10 + 1 = 31.

Data Size and Constraints

For 20% of the test cases, $K = 2$.

For 100% of the test cases, $1 \le N, M \le 500$, $1 \le K \le \min(N \times M, 500)$, $0 \le P_i \le M$, $0 \le B_i \le 10^5$.

Notes

This problem is scored according to the original COCI settings, with a maximum score of $90$.

The problem is translated from COCI2018-2019 CONTEST #6 T3 Sličice.

见题面 Input 部分

见题面 Output 部分