火星政府不仅对优化太空飞行感兴趣,还希望改善地球的道路系统。
火星最重要的高速公路之一连接奥林普城和塞多尼亚首府克斯托洛普。在这个问题中,我们只考虑从 Kstolop 到 Olymp City 的路径,而不考虑反向路径(即从 Olymp City 到 Kstolop 的路径)。
从 Kstolop 到奥林普城的道路长 $$$\ell$$$ 公里。道路上的每个点都有一个坐标 $$$x$$$ ($$$0 \le x \le \ell$$$),等于距 Kstolop 的距离(以公里为单位)。因此,Kstolop 位于坐标 $$$0$$$ 的点,Olymp City 位于坐标 $$$\ell$$$ 的点。
沿路有 $$$n$$$ 标志,其中 $$$i$$$ 设置了速度限制 $$$a_i$$$。此限制意味着下一公里必须在 $$$a_i$$$ 分钟内通过,并且一直有效,直到您遇到沿路的下一公里。道路起点处(即坐标为 $$$0$$$ 的点)有一个路标,用于设置初始速度限制。
如果你知道所有标志的位置,就不难算出从克斯托洛普开车到奥林普城需要多少时间。考虑一个例子:
在这里,你需要在五分钟内行驶前三公里,然后在八分钟内行驶一公里,然后在三分钟内行驶四公里,最后两公里必须在六分钟内行驶。总时间为 $$$3\cdot 5 + 1\cdot 8 + 4\cdot 3 + 2\cdot 6 = 47$$$ 分钟。
为了优化道路交通,玛氏政府决定拆除不超过 $$$k$$$ 的路标。不能去掉路起点的标志,否则起点不限速。通过移除这些标志,政府还希望尽可能缩短从克斯托洛普开车到奥林普城所需的时间。
最大的工业企业都位于Cydonia,因此优化奥林普城的道路交通是首要任务。所以,火星政府希望你按照上述方式去除这些标志。
输入
第一行包含三个整数 $$$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 < d_{i+1}$$$, $$$0 \le d_i \le \ell - 1$$$) — 所有标志的坐标。
第三行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \le a_i \le 10^4$$$) — 速度限制。
输出
打印一个整数 - 如果您移除的路标不超过 $$$k$$$,则从 Kstolop 开车到奥林普城所需的最短时间为几分钟。
示例
输入 #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
注意
在第一个示例中,您无法删除标志。所以答案是 $$$47$$$,正如上面的陈述中所说。
在第二个示例中,您可以删除第二个和第四个符号。在这种情况下,您需要在 $$$4\cdot5 = 20$$$ 分钟内行驶四公里,然后在 $$$6\cdot3 = 18$$$ 分钟内行驶六公里,因此总时间为 $$$4\cdot5 + 6\cdot3 = 38$$$ 分钟。