2023 T2 公路

主知识点：贪心。交叉标签：贪心、前缀和、数学。
暴力标注：不属于重点 DP 退路题。
OJ 使用标准输入与标准输出。原比赛文件名为 road.in / road.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 1 秒；内存 512 MiB；测试点 20；总分 100。
数据来源：公开存档数据；未逐文件对照官网下载包。

题目描述

公路依次有 $n$ 个站点，$i$ 到 $i+1$ 距离为 $v_i$。在第 $i$ 个站买油，每升价为 $a_i$，只能购买整数升，油箱容量不限。每升可行驶 $d$ 公里，起点 1 号站油箱为空。求到达 $n$ 号站的最小加油花费。

输入格式

输入的第一行包含两个正整数 $n$ 和 $d$，分别表示公路上站点的数量和车每升油可以前进的距离。

输入的第二行包含 $n - 1$ 个正整数 $v_1, v_2\dots v_{n-1}$，分别表示站点间的距离。

输入的第三行包含 $n$ 个正整数 $a_1, a_2 \dots a_n$，分别表示在不同站点加油的价格。

输出格式

输出一行，仅包含一个正整数，表示从站点 $1$ 开到站点 $n$，小苞至少要花多少钱加油。

样例

样例 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$。

测试点	$n \leq$	特殊性质
$1\sim 5$	$8$	无
$6\sim 10$	$10^3$
$11\sim 13$	$10^5$	A
$14\sim 16$		B
$17\sim 20$		无

• 特殊性质 A：站点 $1$ 的油价最低。

• 特殊性质 B：对于所有 $1 \leq i < n$，$v_i$ 为 $d$ 的倍数。

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P9749
• 赛事：CSP-J 第二轮入门级 2023。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。