Rt:

#include <bits/stdc++.h>
#define es else 
#define ef es if
using namespace std;

#define ll long long
#define rint register long long

long long N, C, minn;
long long a[1000005], b[1000005], num[1000005];

struct SegmentTree {
    bool flag;
    long long  f, u, sum; 
} tree[8000005];

#define lc(p) (p << 1 | 0)
#define rc(p) (p << 1 | 1)

void merge(long long p)
{
    tree[p].f = min(tree[p << 1].f, tree[(p << 1) | 1].f);
}

void flush_down(long long p)
{
    if(tree[p].flag)
    {
        tree[lc(p)].f = tree[rc(p)].f = tree[p].f;
        tree[lc(p)].u = tree[rc(p)].u = 0;
        tree[lc(p)].sum = tree[rc(p)].sum = 0;
        tree[lc(p)].flag = tree[rc(p)].flag = true;
        tree[p].flag = false;
    }
}

void push_down(long long l, long long r, long long p)
{
    flush_down(p), flush_down(lc(p)), flush_down(rc(p));
    if(tree[p].sum)
    {
        tree[lc(p)].f += tree[p].sum;
        tree[lc(p)].sum += tree[p].sum;
        tree[rc(p)].f += tree[p].sum;
        tree[rc(p)].sum += tree[p].sum;
        tree[p].sum = 0;
    }
    if(tree[p].u)
    {
        long long mid = (l + r) >> 1;
        tree[lc(p)].f += b[mid] * tree[p].u;
        tree[lc(p)].u += tree[p].u;
        tree[rc(p)].f += b[r] * tree[p].u;
        tree[rc(p)].u += tree[p].u;
        tree[p].u = 0;
    }
}

void dp1(long long l, long long r, long long p, long long x, long long val1, long long val2)
{
    long long mid = (l + r) >> 1;
    if(l != r)
        push_down(l, r, p);
    if(r <= x)
    {
        flush_down(p);
        tree[p].f += val1 + b[r];
        tree[p].sum += val1;
        ++ tree[p].u;
        if(r == x) 
            minn = tree[p].f;
    }
    ef(l > x)
    {
        flush_down(p);
        tree[p].f += val2;
        tree[p].sum += val2;
    }
    es
    {
        dp1(l, mid, lc(p), x, val1, val2);
        dp1(mid + 1, r, rc(p), x, val1, val2);
        merge(p);
    }
}

bool dp2(long long l, long long r, long long p, long long x, long long val1)
{
    long long mid = (l + r) >> 1;
    if(l != r)
        push_down(l, r, p);
    if(l > x)
    {
        if(tree[p].f > val1)
        {
            tree[p].f = val1, tree[p].sum = tree[p].u = 0;
            return (tree[p].flag = true);
        }
        if(l != r && dp2(l, mid, lc(p), x, val1)) dp2(mid + 1, r, rc(p), x, val1);
        return false;
    }
    ef(l == r)
        return false;
    ef(x < mid)
    {
        if(dp2(l, mid, lc(p), x, val1)) return dp2(mid + 1, r, rc(p), x, val1);
        else return false;
    }
    
    return dp2(mid + 1, r, rc(p), x, val1);
}

signed main()
{
    cin >> N >> C;
    for(long long i = 1; i <= N; ++ i)
        cin >> a[i], b[i] = a[i];

    sort(b + 1, b + N + 1);
    long long tmp = unique(b + 1, b + N + 1) - (b + 1);
    for(long long i = 1; i <= N; ++ i) 
        num[i] = tmp + 1 - (lower_bound(b + 1, b + tmp + 1, a[i]) - b);

    reverse(b + 1, b + tmp + 1);
    for(long long i = 1; i <= N; ++ i)
    {
        dp1(1, tmp, 1, num[i], -a[i], C);
        dp2(1, tmp, 1, num[i], minn);
    }

    cout << tree[1].f << endl;
    return 0;
}