公路优化

• 时间限制：3 秒
• 内存限制：128 MiB

题目描述

一条从 Kstolop 到奥林匹城的单向公路长为 $\ell$ 千米。公路上的位置用离起点的距离 $x$ 表示，其中 $0\le x\le\ell$。

公路上有 $n$ 个限速标志。第 $i$ 个标志位于 $d_i$，并规定从这里到下一个标志的每千米通行时间为 $a_i$ 分钟。起点 $d_1=0$ 一定有一个标志。

例如，若相邻标志位置依次为 $0,3,4,8$，终点为 $10$，对应的每千米通行时间为 $5,8,3,6$，则总时间为 $3\times5+1\times8+4\times3+2\times6=47$ 分钟。

政府可以移除至多 $k$ 个标志，但不能移除起点标志。标志被移除后，前一个未被移除标志的规定将持续到下一个未被移除标志（或终点）。求从起点到终点的最短通行时间。

输入格式

第一行包含三个整数 $n,\ell,k$（$1\le n\le500$，$1\le\ell\le10^5$，$0\le k\le n-1$）。

第二行包含 $n$ 个整数 $d_i$（$d_1=0$，$d_i<d_{i+1}$，$0\le d_i\le\ell-1$），表示标志位置。

第三行包含 $n$ 个整数 $a_i$（$1\le a_i\le10^4$），表示每千米通行时间。

输出格式

输出一个整数，表示移除至多 $k$ 个标志后的最短通行时间。

样例输入 1

4 10 0
0 3 4 8
5 8 3 6

样例输出 1

47

样例输入 2

4 10 2
0 3 4 8
5 8 3 6

样例输出 2

38

数据范围