#1218. Dw的缅北奇妙冒险

Dw的缅北奇妙冒险

题目背景

Dw 有一天在网上看到了一条赚钱广告,该广告宣称打字一天赚 114514114514 元,于是他前往了广告公司,结果却到了缅甸北部!

Dw 现在有一个喷气背包,他准备逃出缅甸,但是喷气背包喷的时候会消耗氮气,同时在途中有很多 Dw 的朋友给 Dw 提供修复氮气的资源

题目描述

nn 个 Dw 的朋友在路途上等待, Dw 从第一个朋友的位置出发,朋友之间的位置差距分别为 vivi ,同时每个朋友的氮气都只能以整数单位提供,每个整数单位可以让 Dw 前进 dd 距离单位。

不过,每加一整数单位的氮气,都会对喷气背包造成 aiai 点磨损。

现在,请你帮助 Dw 算一算,如果从第一个朋友的位置出发(一开始 Dw 的喷气背包氮气只有 0 ,且他的喷气背包可以容纳最多 26312 ^ {63} - 1 的氮气),飞到第 nn 个朋友处,最少会造成多少点磨损。

输入格式

第一行两个正整数 n,n, dd ,分别表示朋友个数和一整数单位的氮气的飞行距离。

接下来一行 n1n-1 个正整数,分别表示第 ii 个朋友与第 i+1i + 1 个朋友的距离。

接下来一行 nn 个正整数,分别表示第 ii 个朋友每一整数单位的氮气对喷气背包造成的磨损量。

输出格式

只有一行一个正整数,表示最后造成的磨损总量。

样例

输入

5 4
10 10 10 10
9 8 9 6 5

输出

79

样例解释

在此样例中,可以选择在第一个朋友处加 33 整数单位的氮气,在第二个朋友处加 55 整数单位的氮气,最后在第四个朋友处加 22 整数单位的氮气。

数据范围

对于 100100% 的数据,保证 1n,d,vi,ai1051 \leq n, d, vi, ai \leq 10^5