4023 - [COCI 2018-2019 #6] Sličice

Nikola 喜欢收集足球队员的照片，并将其保存在相册中。他计划收集 N 支球队的队员照片，其中每支球队都有 M 张。

对于 Nikola 所收集的每支球队，该球队的照片数量 x 能给他增加分数 B_x。他目前拥有球队 i 的照片数量为 P_i。

Nikola 的好朋友 Ivan 有两套完整的相册。Ivan 决定送 K 张照片给 Nikola。Nikola 想要知道，在得到这 K 张照片之后，它的相册所能得到的分数的最大值。

第一行输入整数 N,M,K。

第二行输入 N 个整数 P_i。

第三行输入 M+1 个整数 B_i，其中 B_i 表示一支球队收集到了 ii 张不同的照片能够获得 B_i 分。

对于 [0,M-1] 内的每一个整数 t，都满足 B_t \le B_{t+1}。同时 K \le N \times M-\sum_{i=1}^N P_i。

输出能够得到的分数的最大值。

样例一解释

Nikola 一开始拥有球队 1,2,3,4 照片数量分别为 4,2,3,1。最优的方案是获得球队 2,3 照片各 1 张。此时分数最大，为 10+10+10+1=31。

数据范围

对于 20\% 的数据，K=2。

对于 100\% 的数据，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。