#h. 道路优化

传统题

1000ms

256MiB

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

题目描述

火星政府不仅对优化太空飞行感兴趣，还希望改善地球的道路系统。

火星最重要的高速公路之一连接奥林匹亚城和西多尼亚首府克斯托洛普。在这个问题中，我们只考虑从 A city 到 B city 的路径。

从 A city 到 B city 的道路是 $l$ 公里。道路的每个点都有一个坐标 $x，(0≤x≤l)$ ，等于距 A city 的距离（以公里为单位）。因此，A city 位于坐标点 $0$ ，而 B city 位于坐标的点 $l$ 。

路上有 $n$ 个限速点，(第一个限速点在起点)，第 $i$ 个限速点位置在 $d_i$ ，限速值为 $a_i$ ，表示从这个限速点到下个限速点位置，每经过一千米需要花费 $a_i$ 点单位时间。

你最多可以删掉 $k$ 个限速点，请问删除后到达目标城市的最短时间是多少？

如果您知道所有标志的位置，就不难计算从 A city 开车到 B city 需要多少时间。来看一个例子：

在这里，您需要在每公里五分钟内行驶前三公里，然后在八分钟内行驶一公里，然后在每分钟内行驶四公里，最后必须在六分钟内通过最后两公里。总时间为3⋅5+1⋅8+4⋅3+2⋅6=47。

第一行三个整数， $n,l,k$ 。

第二行 $n$ 个整数， $d_i$ 表示第 $i$ 个限速点的位置。

第三行 $n$ 个整数， $a_i$ 经过第 $i$ 个限速点后的限速值。

$(1≤n≤500,1≤l≤10^5,0≤k≤n-1)$ 。

$d_1=0,d_i<d_{i+1}, 0≤ d_i ≤l-1$ 。 $1≤ a_i ≤ 10^4$ 。

4 10 0
0 3 4 8
5 8 3 6

4 10 2
0 3 4 8
5 8 3 6

样例数据 $2$ ，删除 2，4 限速点。