Nikola 是一位热衷于收集足球运动员卡片集卡册的收藏家。他和他的朋友们根据当前正在收集的集卡册，发明了一款游戏并互相竞争。该集卡册中的卡片分为 $N$ 个队伍，每个队伍恰好有 $M$ 名足球运动员。游戏的主要规则是，一个人在第 $i$ 个队伍上获得的总分数为 $B_x$，其中 $x$ 是该人收集到的该队伍的不同足球运动员卡片总数。他们还约定数组 $B$ 是单调不减的，即拥有某个队伍更多数量的不同卡片意味着获得大于或等于原先的分数。

Nikola 希望在游戏中获得尽可能多的分数。对于每个队伍 $x$，已知 Nikola 当前拥有的该队伍的不同卡片数量为 $P_x$。

Ivan 是 Nikola 的朋友，他已经集满了整套集卡册两次。当他听说 Nikola 和朋友们玩的这个游戏后，他决定送给 Nikola 任意他想要的 $K$ 张卡片。得知这个好消息后，Nikola 想知道在 Ivan 送给他 $K$ 张卡片后，他最多能获得多少分。他太兴奋了，以至于无法计算，于是请求你帮他回答这个问题。

输入格式

第一行包含三个整数 $N$、$M$ 和 $K$（$1 \le N, M \le 500$，$1 \le K \le \min(N \cdot M, 500)$），含义如题面所述。

第二行包含一个由 $N$ 个非负整数组成的数组 $P$（$0 \le P_i \le M$）。

第三行包含一个由 $M+1$ 个非负整数组成的数组 $B$（$0 \le B_i \le 100\,000$），表示一个队伍拥有 $i$（$0 \le i \le M$）张不同的卡片时 Nikola 可以获得的分数。

对于 $0$ 到 $M-1$ 之间的每个 $t$，均满足 $B_t \le B_{t+1}$。

保证 $K \le N \cdot M - (P_1 + P_2 + \dots + P_N)$。

输出格式

输出唯一的一行，表示 Nikola 问题的答案（即最大可能获得的总分数）。

子任务

在占总分 20% 的测试样例中，满足 $K = 2$。

样例

输入样例 1

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

输出样例 1

31

样例 1 说明

Nikola 最好的选择是让 Ivan 给他一张第三个队伍的卡片和两张第二个队伍的卡片，这样他的总得分将是 $31$（$10 + 10 + 10 + 1$）。

输入样例 2

4 3 5
1 1 2 3
0 1 2 3

输出样例 2

12

输入样例 3

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

输出样例 3

206