Goods transportation

时间：2021-04-06 10:47:17
Goods transportation
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 pi units of goods. No more than si units of goods can be sold in the i-th city.

For each pair of cities i and j such that 1 ≤ i < 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.

Input

The first line of the input contains two integers n and c (1 ≤ n ≤ 10 000, 0 ≤ c ≤ 109) — the number of cities and the maximum amount of goods for a single transportation.

The second line contains n integers pi (0 ≤ pi ≤ 109) — the number of units of goods that were produced in each city.

The third line of input contains n integers si (0 ≤ si ≤ 109) — the number of units of goods that can be sold in each city.

Output

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

Examples
input
3 0
1 2 3
3 2 1
output
4
input
5 1
7 4 2 1 0
1 2 3 4 5
output
12
input
4 3
13 10 7 4
4 7 10 13
output
34
分析：考虑最大流等于最小割，从小到大dp；
　　　dp[i][j]表示前i个点有j个点在最小割点集里，
　　　则dp[i][j]=min(dp[i-1][j-1]+s[i],dp[i-1][j]+j*c+p[i]);
　　　dp[i-1][j-1]+s[i]表示i留在s-割的代价，dp[i-1][j]+j*c+p[i]表示i留在t-割，除了要花费p[i]外，还要花费j*c的代价；
代码：
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <climits>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <vector>

#include <list>

#define rep(i,m,n) for(i=m;i<=n;i++)

#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)

#define mod 1000000007

#define inf 0x3f3f3f3f

#define vi vector<int>

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define ll long long

#define pi acos(-1.0)

#define pii pair<ll,int>

#define Lson L, mid, ls[rt]

#define Rson mid+1, R, rs[rt]

const int maxn=1e5+;

using namespace std;

ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}

ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p;p=p*p;q>>=;}return f;}

inline ll read()

{

    ll x=;int f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int n,m,k,t;

ll p[maxn],s[maxn],ans[maxn],c;

int main()

{

    int i,j;

    scanf("%d%lld",&n,&c);

    rep(i,,n)scanf("%lld",&p[i]);

    rep(i,,n)scanf("%lld",&s[i]);

    rep(i,,n)

    {

        ans[i]=1e18;

        for(j=i;j>=;j--)

        {

            ans[j]=min(ans[j]+j*c+p[i],ans[j-]+s[i]);

        }

        ans[]+=p[i];

    }

    ll ret=1e18;

    rep(i,,n)ret=min(ret,ans[i]);

    printf("%lld\n",ret);

    //system("Pause");

    return ;

}

相关文章