该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

"わかります"(我懂的)

最终的Revue正在进行，但此时长颈鹿的车被堵在了繁忙的东京都，距离舞台还有$l$公里，它现在心急如焚，希望尽快到达舞台。

但是东京都的限速规定十分严格。沿路共有$n$个限速标志,上面标明了$a_i$,表示接下来的路途中走过每公里用时不得少于$a_i$分钟，直到下一个路标出现，下一个路标的限速$a_{i+1}$成为接下来路途中的限速。最后一个标志的限速一直持续路途结束，路途的起点有一个标志，表示最开始的限速。

举个栗子：

在图中的场景下，开始的三公里，每公里最少走五分钟；接下来一公里，每公里最少走八分钟；接下来四公里，每公里最少走三分钟；最后一公里，每公里最少用六分钟。于是一共用时 $3 ⋅ 5 + 1 ⋅ 8 + 4 ⋅ 3 + 2 ⋅ 6 = 47$ 分钟。

无所不能的长颈鹿决定动用一点手段，让自己堵在路上的时间压缩到最短。它最多可以选择$k$个限速标志并拆除它们，但不能拆除起点，否则一开始将没有限速。它希望你帮他选择合适的限速标志，使得拆除后它能最快到达舞台，如果你能做出来，它会允许你在它旁边欣赏Revue（x）。

Input Format

第一行包含三个整数 $n,l,k(1≤n≤500, 1≤l≤10^5, 0≤k≤n−1)$ ,分别表示道路上的标志数量，起点与终点之间的距离，以及你可以移除的最大标志数量。

第二行包含$n$个整数 $d_i（d_1=0，d_i<d_{i+1}，0≤d_i≤l-1）$ ,表示所有符号的坐标。

第三行包含$n$个整数 $a_i (1≤a_i≤10^4)$ ,表示限速。

Output Format

共一行，表示拆除标志后花费的最短时间。

Sample

Sample1

Sample Input

4 10 0
0 3 4 8
5 8 3 6

Sample Output

47

Sample2

Sample Input

4 10 2
0 3 4 8
5 8 3 6

Sample Output

38

Hint

对于 $20\%$ 的数据，保证 $1≤n≤8$，

对于另外 $5\%$ 的数据，保证 $k=0$，

对于另外 $10\%$ 的数据，保证 $k=1$，

对于另外 $10\%$ 的数据，保证相邻路标之间的距离相等，

对于 $100\%$ 的数据，保证 $1≤n≤500, 1≤l≤10^5, 0≤k≤n−1, d_1=0, a_i≤10^4$