Problem Description

Nikola likes collecting photos of football players and keeping them in an album. He plans to collect player photos from $N$ teams, and each team has $M$ photos.

For each team that Nikola collects, if the number of photos he has from that team is $x$, he gains $B_x$ points. Currently, the number of photos he has from team $i$ is $P_i$.

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

Input Format

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

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

The third line contains $M+1$ integers $B_i$, where $B_i$ means that collecting $i$ different photos from a team gives $B_i$ points.

For every integer $t$ in $[0, M-1]$, it holds that $B_t \le B_{t+1}$. Also, $K \le N \times M-\sum_{i=1}^N P_i$.

Output Format

Output the maximum total score that can be obtained.

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

31

4 3 5
1 1 2 3
0 1 2 3

12

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

206

Hint

Sample 1 Explanation

At the beginning, Nikola has $4, 2, 3, 1$ photos from teams $1, 2, 3, 4$, respectively. The best plan is to get $2$ photos from team $2$ and $1$ photo from team $1$. Then the score is maximized, equal to $10+10+10+1=31$.

Constraints

For $20\%$ of the testdata, $K=2$.

For $100\%$ of the testdata, $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

The scoring of this problem follows the original COCI problem settings, with a full score of $90$.

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

Translated by ChatGPT 5