#include<stdlib.h>
#include<string.h>
#define Nm 1024
#define Inf 2000000000
#define abs(a) ((a)<0?-(a):(a))
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
int H[Nm],C[Nm],n,k,hm;

void generate()
{
    int i;

    n=1000; k=153453543;
    srand(77);
    for(i=1;i<=n;++i)
    {
        H[i]=rand()%1000+1;
        C[i]=rand()%1000+1;
    }
}

int cmin(int m)
{
    int A[2][Nm],l,r,i,j,c,p,v;
    struct
    {
        int v,p;
    } D[Nm];

    memset(A[0],0,sizeof(A[0]));
    for(c=1,p=0,i=n-1;i;--i,c^=1,p^=1)
    {
        l=1; r=0;
        for(j=0;j<=m && j<=hm;++j)
        {
            v=abs(H[i+1]-j)*C[i+1]+A[p][j];
            while(l<=r && v<D[r].v)
                --r;
            D[++r].v=v; D[r].p=j;
        }
        A[c][0]=D[1].v;

        for(j=1;j<=hm;++j)
        {
            if(j+m<=hm)
            {
                v=abs(H[i+1]-j-m)*C[i+1]+A[p][j+m];
                while(l<=r && v<D[r].v)
                    --r;
                D[++r].v=v; D[r].p=j+m;
            }
            if(D[l].p<j-m)
                ++l;
            A[c][j]=D[l].v;
        }
    }

    i=Inf;
    for(j=0;j<=hm;++j)
        i=min(i,abs(H[1]-j)*C[1]+A[p][j]);
    return i;
}

void solve()
{
    int i,j=0,m;

    hm=H[n];
    for(i=1;i<n;++i)
    {
        j=max(j,abs(H[i]-H[i+1]));
        hm=max(hm,H[i]);
    }

    i=0;
    while(i<j)
    {
        m=i+j>>1;
        if(cmin(m)<=k)
            j=m;
        else
            i=m+1;
    }
}

int main()
{
    generate();
    solve();
    return 0;
}