Goods transportation

题意翻译

小明升任了 CF 国的大总管,他管辖的 $n$ 个城市,编号为 $1..n$ 。每个城市生产了 $p_i$ 个货物,限制最多可以卖掉 $s_i$ 个货物。对于每两个城市 $i, j$ ,如果 $i < j$ ,则可以最多从 $i$ 运送 $c$ 个货物到 $j$ 。注意不能反向运送,却可以在多个城市之间送来送去。现在小明想知道,经过运输后,最多能卖掉多少个货物。 感谢@larryzhong 提供的翻译

题目描述

There are $ n $ cities located along the one-way road. Cities are numbered from $ 1 $ to $ n $ in the direction of the road. The $ i $ -th city had produced $ p_{i} $ units of goods. No more than $ s_{i} $ units of goods can be sold in the $ i $ -th city. For each pair of cities $ i $ and $ j $ such that $ 1<=i&lt;j<=n $ you can no more than once transport no more than $ c $ units of goods from the city $ i $ to the city $ j $ . Note that goods can only be transported from a city with a lesser index to the city with a larger index. You can transport goods between cities in any order. Determine the maximum number of produced goods that can be sold in total in all the cities after a sequence of transportations.

输入输出格式

输入格式


The first line of the input contains two integers $ n $ and $ c $ ( $ 1<=n<=10000 $ , $ 0<=c<=10^{9} $ ) — the number of cities and the maximum amount of goods for a single transportation. The second line contains $ n $ integers $ p_{i} $ ( $ 0<=p_{i}<=10^{9} $ ) — the number of units of goods that were produced in each city. The third line of input contains $ n $ integers $ s_{i} $ ( $ 0<=s_{i}<=10^{9} $ ) — the number of units of goods that can be sold in each city.

输出格式


Print the maximum total number of produced goods that can be sold in all cities after a sequence of transportations.

输入输出样例

输入样例 #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