P7381 [COCI 2018/2019 #6] Sličice

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.

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 the maximum total score that can be obtained.

#### 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](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #6](https://hsin.hr/coci/archive/2018_2019/contest6_tasks.pdf) _T3 Sličice_.** Translated by ChatGPT 5