#2371. [CSP-J 2023] 公路

[CSP-J 2023] 公路

题目描述

小苞准备开着车沿着公路自驾。

公路上一共有 nn 个站点,编号为从 11nn。其中站点 ii 与站点 i+1i + 1 的距离为 viv_i 公里。

公路上每个站点都可以加油,编号为 ii 的站点一升油的价格为 aia_i 元,且每个站点只出售整数升的油。

小苞想从站点 11 开车到站点 nn,一开始小苞在站点 11 且车的油箱是空的。已知车的油箱足够大,可以装下任意多的油,且每升油可以让车前进 dd 公里。问小苞从站点 11 开到站点 nn,至少要花多少钱加油?

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

5 4
10 10 10 10
9 8 9 6 5

样例输出 #1

79

提示

【样例 1 解释】

最优方案下:小苞在站点 11 买了 33 升油,在站点 22 购买了 55 升油,在站点 44 购买了 22 升油。

【样例 2】

见选手目录下的 road/road2.in 与 road/road2.ans。

【数据范围】

对于所有测试数据保证:1n1051 \leq n \leq 10^51d1051 \leq d \leq 10^51vi1051 \leq v_i \leq 10^51ai1051 \leq a_i \leq 10^5

测试点 nn \leq 特殊性质
151\sim 5 88
6106\sim 10 10310^3
111311\sim 13 10510^5 A
141614\sim 16 B
172017\sim 20
  • 特殊性质 A:站点 11 的油价最低。
  • 特殊性质 B:对于所有 1i<n1 \leq i < nviv_idd 的倍数。