采用文件输入输出

题目描述

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$ 表示一支球队收集到了 $i$ 张不同的照片能够获得 $B_i$ 分。

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

31

输入输出样例 #2

输入 #2

4 3 5
1 1 2 3
0 1 2 3

输出 #2

12

输入输出样例 #3

输入 #3

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

输出 #3

206

说明/提示

样例 1 解释

Nikola 一开始拥有球队 $1,2,3,4$ 照片数量分别为 $4,2,3,1$。最优的方案是获得球队 $2,3$ 照片分别 $2, 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$。