A7124.公路

普及-

CSP-J

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

公路上一共有 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

    5 4
    10 10 10 10
    9 8 9 6 5

    输出#1

    79

说明/提示

【样例 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 10510^5 B
172017\sim 20 10510^5
  • 特殊性质 A:站点 11 的油价最低。
  • 特殊性质 B:对于所有 1i<n1 \leq i < nviv_idd 的倍数。

输入文件名:road.in
输出文件名:road.out

首页