小苞准备开着车沿着公路自驾。
公路上一共有 n nn 个站点，编号为从 1 11 到 n nn。其中站点 i ii 与站点 i + 1 i + 1i+1 的距离为 v i v_ivi 公里。
公路上每个站点都可以加油，编号为 i ii 的站点一升油的价格为 a i a_iai 元，且每个站点 只出售整数升的油。
小苞想从站点 1 11 开车到站点 n nn，一开始小苞在站点 1 11 且车的油箱是空的。已知车的 油箱足够大，可以装下任意多的油，且每升油可以让车前进 d dd 公里。问小苞从站点 1 11 开 到站点 n nn，至少要花多少钱加油？
注意：本题测试数据由AKOJ自研，数据随机。
