有 n 个城市位于单向公路沿线。城市沿道路方向从 1 到 n 编号。
第 i 个城市生产了 pi 单位的商品。第 i 个城市最多可销售 si 单位的商品。
对于每对城市 i 和 j,且 1 ≤ i < j ≤ n,您最多只能从城市 i 向城市 j 运输不超过 c 单位的货物。请注意,货物只能从指数较小的城市运输到指数较大的城市。您可以按任何顺序在城市之间运输货物。
确定经过一系列运输后,所有城市总共可以销售的最大生产商品数量。
输入
输入的第一行包含两个整数 n 和 c (1 ≤ n ≤ 10 000, 0 ≤ c ≤ 109)——城市数量和单次运输的最大货物数量。
第二行包含 n 个整数 pi (0 ≤ pi ≤ 109) — 每个城市生产的商品单位数。
输入的第三行包含n个整数si (0 ≤ si ≤ 109)——每个城市可以销售的商品单位数。
输出
打印一系列运输后可在所有城市销售的最大生产商品总数。
示例
输入 #1
3 0 1 2 3 3 2 1
输出 #1
4
输入 #2
5 1 7 4 2 1 0 1 2 3 4 5
输出 #2
12
输入 #3
4 3 13 10 7 4 4 7 10 13
输出 #3
34