题目描述(ID:12327)
标题: 货物运输
标签:
详情:
A公司分别在编号1-n的城市都设有工厂,编号为i的城市中的工厂的产量为pi。同时,每个城市都有一定的消费能力,编号为i的城市最多购买si的产品。
A公司可以把一个城市的货物运往另一个城市,但只能从小编号的城市运向更大编号的城市,且每次最多运输c个单位的货物。即对于所有的i<j,都可以从编号为i的城市最多运送c个单位的货物到编号为j的城市。
你可以以任意的顺序运送货物,但每对城市(i,j)之间只能进行一次运输。现在A公司的老总想知道A公司最多能卖出去多少货物。
输入格式:
第一行包括两个整数n,c,含义见上。
第二行包括n个整数p[1...n],代表每个城市中的工厂的产量。
第三行包括n个整数s[1...n],代表每个城市的最大销量。
输出格式:
输出一个整数,代表A公司的最大销量。
限制: 对于10%的数据,c=0
对于60%的数据,n<=100,0<=c,si,pi<=10^5
对于80%的数据,n<=3000
对于100%的数据,n<=100000,0<=c,si,pi<=10^9
样例:

输入

3 0
1 2 3
3 2 1

输出

4

输入

5 1
7 4 2 1 0
1 2 3 4 5

输出

12

输入

4 3
13 10 7 4
4 7 10 13

输出

34
登录并解答