有按顺序排列的 $n$ 个加油站，相邻站点 $i$ 与 $i+1$ 的距离为 $v_i$。每升油可以行驶 $d$ 公里，各站油价为 $a_i$。

购买量必须为整数升，油箱容量不限，出发时油箱为空。求从站点 $1$ 行驶到站点 $n$ 的最小费用。

输入格式

第一行包含两个整数 $n,d$。

第二行包含 $n-1$ 个距离 $v_1,v_2,\dots,v_{n-1}$。第三行包含 $n$ 个价格 $a_1,a_2,\dots,a_n$。当 $n=1$ 时，距离序列为空。

输出格式

输出一个整数，表示最小总费用。

样例 1

5 4
10 10 10 10
9 8 9 6 5

79

数据范围与原题特殊限制

对于所有测试数据保证：$1 \leq n \leq 10^5$，$1 \leq d \leq 10^5$，$1 \leq v_i \leq 10^5$，$1 \leq a_i \leq 10^5$。

• 特殊性质 A：站点 $1$ 的油价最低。
• 特殊性质 B：对于所有 $1 \leq i < n$，$v_i$ 为 $d$ 的倍数。

来源与数据说明

原题页面。以上题意为重新整理的表述，规则、输入输出和约束与原题一致。本题使用独立生成的训练数据，原题测试点表仅说明原比赛范围与特殊性质，本包评分不复刻官方测试点分布。标准输入输出，不要求文件读写。