老佩坎居住的国家有 n 个城市。这些城市位于一条直线上,我们从左到右将它们表示为c1,c2,...,cn。 Old Peykan 希望通过道路从城市 c1 前往 cn。有(n - 1)条单向道路,第i条路从城市ci到城市ci+1,长di公里。
Old Peykan 在 1 小时内行驶 1 公里,在此期间消耗 1 升燃油。
每个城市 ci(最后一个城市 cn 除外)都有 si 升的燃料供应,如果经过该城市或停留在该城市,这些燃料会立即转移到老佩坎。该供应量在传输后 k 小时后立即刷新。老佩坎可以在城市停留一段时间,并多次加满油箱。
最初(时间为零时)Old Peykan 位于城市 c1,并且 s1 升燃料从 c1 的供应转移到其空油箱中。 Old Peykan 的油箱容量是无限的。如果老佩坎的油箱在两个城市之间严格清空,则无法继续行驶。
求 Old Peykan 到达城市 cn 所需的最短时间。
输入
输入的第一行包含两个空格分隔的整数 m 和 k (1 ≤ m, k ≤ 1000)。 m 值指定城市之间的道路数量,等于 n - 1。
下一行包含 m 个空格分隔的整数 d1, d2, ..., dm (1 ≤ di ≤ 1000),下一行包含 m 个空格分隔的整数 s1, s2, ..., sm (1 ≤ si ≤ 1000)。
输出
在输出的唯一一行中打印一个整数 — The Old Peykan 从城市 c1 到达城市 cn 所需的最短时间。
示例
输入 #1
4 6 1 2 5 2 2 3 3 4
输出 #1
10
输入 #2
2 3 5 6 5 5
输出 #2
14
注意
在上面的第二个示例中,Old Peykan 在 c1 中停留了 3 小时。