CF1625C.Road Optimization

The Government of Mars is not only interested in optimizing space flights, but also wants to improve the road system of the planet.

One of the most important highways of Mars connects Olymp City and Kstolop, the capital of Cydonia. In this problem, we only consider the way from Kstolop to Olymp City, but not the reverse path (i. e. the path from Olymp City to Kstolop).

The road from Kstolop to Olymp City is $\ell$ kilometers long. Each point of the road has a coordinate $x$ ($0 \le x \le \ell$), which is equal to the distance from Kstolop in kilometers. So, Kstolop is located in the point with coordinate $0$, and Olymp City is located in the point with coordinate $\ell$.

There are $n$ signs along the road, $i$-th of which sets a speed limit $a_i$. This limit means that the next kilometer must be passed in $a_i$ minutes and is active until you encounter the next along the road. There is a road sign at the start of the road (i. e. in the point with coordinate $0$), which sets the initial speed limit.

If you know the location of all the signs, it's not hard to calculate how much time it takes to drive from Kstolop to Olymp City. Consider an example:

Here, you need to drive the first three kilometers in five minutes each, then one kilometer in eight minutes, then four kilometers in three minutes each, and finally the last two kilometers must be passed in six minutes each. Total time is $3\cdot 5 + 1\cdot 8 + 4\cdot 3 + 2\cdot 6 = 47$ minutes.

To optimize the road traffic, the Government of Mars decided to remove no more than $k$ road signs. It cannot remove the sign at the start of the road, otherwise, there will be no limit at the start. By removing these signs, the Government also wants to make the time needed to drive from Kstolop to Olymp City as small as possible.

The largest industrial enterprises are located in Cydonia, so it's the priority task to optimize the road traffic from Olymp City. So, the Government of Mars wants you to remove the signs in the way described above.

火星政府不仅关注优化太空飞行，还希望改善该星球的道路系统。

火星一条极为重要的高速公路连接奥林匹亚城（Olymp City）与赛东尼亚首府克斯特洛普（Kstolop）。本题中，我们仅考虑从克斯特洛普到奥林匹亚城的方向（即不考虑从奥林匹亚城到克斯特洛普的反向路径）。

从克斯特洛普到奥林匹亚城的道路全长为 $\ell$ 千米。道路上每一点具有坐标 $x$（$0 \le x \le \ell$），其值表示该点距克斯特洛普的距离（单位：千米）。因此，克斯特洛普位于坐标 $0$ 处，而奥林匹亚城位于坐标 $\ell$ 处。

道路沿线共设有 $n$ 个限速标志，其中第 $i$ 个标志设定限速值 $a_i$。该限速值表示：从该标志起始的接下来 1 千米路段必须耗时 $a_i$ 分钟；该限速持续生效，直至遇到沿道路方向的下一个标志为止。道路起点（即坐标为 $0$ 的位置）处设有一个限速标志，用以设定初始限速。

若已知所有标志的位置，则可轻易计算出从克斯特洛普驾车至奥林匹亚城所需总时间。以下是一个示例：

在此例中，前 3 千米每千米需耗时 5 分钟，接着 1 千米需耗时 8 分钟，再之后 4 千米每千米需耗时 3 分钟，最后 2 千米每千米需耗时 6 分钟。总耗时为 $3\cdot 5 + 1\cdot 8 + 4\cdot 3 + 2\cdot 6 = 47$ 分钟。

为优化道路交通，火星政府决定最多移除 $k$ 个道路标志。但道路起点处的标志不得移除，否则起点将无速度限制。通过移除这些标志，火星政府还希望使从克斯特洛普到奥林匹亚城的行驶时间尽可能短。

由于最大的工业企业均位于赛东尼亚，因此优化从奥林匹亚城出发的道路交通是首要任务。故火星政府要求你按上述方式移除标志。

The first line contains three integers $n$, $\ell$, $k$ ($1 \le n \le 500$, $1 \le \ell \le 10^5$, $0 \le k \le n-1$), the amount of signs on the road, the distance between the cities and the maximal number of signs you may remove.

The second line contains $n$ integers $d_i$ ($d_1 = 0$, $d_i \lt d_{i+1}$, $0 \le d_i \le \ell - 1$) — coordinates of all signs.

The third line contains $n$ integers $a_i$ ($1 \le a_i \le 10^4$) — speed limits.

第一行包含三个整数 $n$、$\ell$、$k$（$1 \le n \le 500$，$1 \le \ell \le 10^5$，$0 \le k \le n-1$），分别表示道路上的标志牌数量、两座城市之间的距离，以及你最多可以移除的标志牌数量。

第二行包含 $n$ 个整数 $d_i$（满足 $d_1 = 0$，$d_i \lt d_{i+1}$，且 $0 \le d_i \le \ell - 1$），表示所有标志牌的坐标。

第三行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^4$），表示各路段对应的速度限制。

Print a single integer — minimal possible time to drive from Kstolop to Olymp City in minutes, if you remove no more than $k$ road signs.

输出一个整数——在最多移除 $k$ 个路标的情况下，从克斯特洛普（Kstolop）驾车到达奥林匹亚市（Olymp City）所需的最少时间（单位：分钟）。

In the first example, you cannot remove the signs. So the answer is $47$, as it's said in the statements above.

In the second example, you may remove the second and the fourth sign. In this case, you need to drive four kilometers in $4\cdot5 = 20$ minutes, and then six kilometers in $6\cdot3 = 18$, so the total time is $4\cdot5 + 6\cdot3 = 38$ minutes.

在第一个例子中，你不能移除任何标志。因此答案是 $47$，如上述题干所述。

在第二个例子中，你可以移除第二个和第四个标志。此时，你需要先行驶四千米，耗时 $4\cdot5 = 20$ 分钟，再行驶六千米，耗时 $6\cdot3 = 18$ 分钟，因此总耗时为 $4\cdot5 + 6\cdot3 = 38$ 分钟。