#764. [CSP-J2023 B] 公路

[CSP-J2023 B] 公路

题目描述

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

公路上一共有 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,小苞至少要花多少钱加油。

10 10 10 10
9 8 9 6 5
79

输入/输出数据 2

见选手目录下的 road2.inroad2.ans

样例 1 解释

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

数据范围

对于所有测试数据保证: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 的倍数。