#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

class A {
public:
    void solve() {
        int n, a[100005] = {}, d[100005] = {};
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        d[1] = 0;
        d[2] = abs(a[1] - a[2]);
        for (int i = 3; i <= n; i++) {
            d[i] = min(d[i - 2] + abs(d[i - 2] - a[i]), d[i - 1] + abs(a[i - 1] - a[i]));
        }
        cout << d[n];
    }
};

class B {
public:
    void solve() {
        int n, k, a[100005] = {}, d[100005] = {};
        cin >> n >> k;
        for (int i = 1; i <= n; i++) cin >> a[i], d[i] = mod;
        for (int i = 1; i <= k; i++) d[i] = abs(a[1] - a[i]);
        for (int i = k + 1; i <= n; i++) for (int j = 1; j <= k; j++) {
            d[i] = min(d[i - j] + abs(a[i - j] - a[i]), d[i]);
        }
        cout << d[n];
    }
};

class C {
public:
    void solve() {
        int n, a[100005][3] = {}, d[100005][3] = {};
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i][0] >> a[i][1] >> a[i][2];
        for (int i = 1; i <= n; i++) {
            d[i][0] = max(d[i - 1][1], d[i - 1][2]) + a[i][0];
            d[i][1] = max(d[i - 1][2], d[i - 1][0]) + a[i][1];
            d[i][2] = max(d[i - 1][0], d[i - 1][1]) + a[i][2];
        }
        cout << max({d[n][0], d[n][1], d[n][2]});
    }
};

class D {
public:
    void solve() {
        int n, w, a[102] = {}, b[102] = {};
        ll z = 0, d[100005] = {};
        cin >> n >> w;
        for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
        for (int i = 0; i < n; i++) for (int j = w; j >= a[i]; j--) d[j] = max(d[j], d[j - a[i]] + b[i]);
        for (int i = 1; i <= w; i++) z = max(z, d[i]);
        cout << z;
    }
};

class E {
public:
    void solve() {
        int n, a[102] = {}, b[102] = {};
        ll w, d[100005] = {};
        cin >> n >> w;
        for (int i = 1; i <= 100000; i++) d[i] = mod * 328ll;
        for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
        for (int i = 0; i < n; i++) for (int j = 100000; j >= b[i]; j--) d[j] = min(d[j], d[j - b[i]] + a[i]);
        for (int i = 100000; i >= 0; i--) if (d[i] <= w) {
            cout << i;
            break;
        }
    }
};

class F {
public:
    void solve() {
        string s, t, u;
        cin >> s >> t;
        int d[3003][3003] = {}, n = (int)s.length(), m = (int)t.length();
        for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) d[i][j] = d[i - 1][j - 1] + 1;
            else d[i][j] = max(d[i - 1][j], d[i][j - 1]);
        }
        while (n && m) {
            if (d[n - 1][m - 1] + 1 == d[n][m]) n--, m--, u += s[n];
            else if (n && d[n - 1][m] == d[n][m]) n--;
            else m--;
        }
        reverse(u.begin(), u.end());
        cout << u;
    }
};

class G {
public:
    void solve() {
        int n, m, u, v, z = 0, c[100005] = {}, d[100005] = {};
        vector<int> g[100005] = {};
        cin >> n >> m;
        for (int i = 0; i < n; i++) cin >> u >> v, g[u].push_back(v), c[v]++;
        queue<int> q;
        for (int i = 1; i <= n; i++) if (!c[i]) q.push(i);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (int i : g[x]) {
                d[i] = max(d[i], d[x] + 1);
                c[i]--;
                if (!c[i]) q.push(i);
            }
        }
        for (int i = 1; i <= n; i++) z = max(z, d[i]);
        cout << z;
    }
};

class H {
public:
    void solve() {
        int n, m, d[1003][1003] = {1};
        string s[1003] = {};
        cin >> n >> m;
        for (int i = 0; i < n; i++) cin >> s[i];
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (s[i][j] == '.') {
            if (i) d[i][j] += d[i - 1][j];
            if (j) d[i][j] += d[i][j - 1];
            if (d[i][j] >= mod) d[i][j] -= mod;
        }
        cout << d[n - 1][m - 1];
    }
};

class I {
public:
    void solve() {
        int n;
        double z = 0, a[3003] = {}, d[3003] = {1};
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) for (int j = n; j >= 0; j--) {
            double e = d[j];
            if (j) d[j] = d[j - 1] * a[i];
            else d[j] = 0;
            d[j] += e * (1 - a[i]);
        }
        for (int i = 0; i <= n; i++) if (i + i > n) z += d[i];
        cout << setprecision(13) << z;
    }
};

class J {
public:
    void solve() {
        int n, c0, c[4] = {};
        double d[303][303][303] = {};
        cin >> n;
        for (int i = 0; i <= n; i++) for (int j = 0; j <= i; j++) for (int k = 0; k <= j; k++) {
            if (i - j) d[i][j][k] += d[i - 1][j][k] * (i - j) / i;
            if (j - k) d[i][j][k] += d[i][j - 1][k] * (j - k) / i;
            if (k) d[i][j][k] += d[i][j][k - 1] * k / i;
            if (i) d[i][j][k] += 1.0 * n / i;
        }
        for (int i = 0; i < n; i++) cin >> c0, c[c0]++;
        cout << setprecision(13) << d[c[1] + c[2] + c[3]][c[2] + c[3]][c[3]];
    }
};

class K {
public:
    void solve() {
        int n, k, a[102] = {}, b[100005] = {};
        cin >> n >> k;
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 1; i <= k; i++) for (int j = 0; j < n; j++) if (i >= a[j]) b[i] |= !b[i - a[j]];
        cout << (b[k] ? "First" : "Second");
    }
};

class L {
public:
    void solve() {
        int n;
        ll a[3003] = {}, d[2][3003][3003] = {};
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) for (int j = 0; j + i < n; j++) {
            d[0][j][j + i] = max(d[1][j + 1][j + i] + a[j], d[1][j][j + i - 1] + a[j + i]);
            d[1][j][j + i] = min(d[0][j + 1][j + i], d[0][j][j + i - 1]);
        }
        cout << d[0][0][n - 1] - d[1][0][n - 1];
    }
};

class M {
public:
    void solve() {
        int n, k, a[102] = {};
        ll d[100005] = {1};
        cin >> n >> k;
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int j = 0; j < n; j++) {
            ll e[100005] = {};
            for (int i = 0; i <= k; i++) e[i] = d[i];
            for (int i = 1; i <= k; i++) e[i] += e[i - 1];
            for (int i = 0; i <= k; i++) d[i] = e[i] - (i > a[j] ? e[i - a[j] - 1] : 0);
            for (int i = 0; i <= k; i++) d[i] %= mod;
        }
        cout << d[k];
    }
};

class N {
public:
    void solve() {
        int n;
        ll a[403] = {}, b[403] = {}, d[403][403] = {};
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i], b[i] = b[i - 1] + a[i];
        for (int i = 0; i < 403; i++) for (int j = 0; j < 403; j++) d[i][j] = mod * 890328ll;
        for (int i = 1; i <= n; i++) d[i][i] = 0;
        for (int i = 1; i < n; i++) for (int j = 1; j + i <= n; j++) {
            for (int k = j; k < j + i; k++) d[j][j + i] = min(d[j][j + i], d[j][k] + d[k + 1][j + i]);
            d[j][j + i] += b[j + i] - b[j - 1];
        }
        cout << d[1][n] << '\n';
    }
};

class O {
public:
    void solve() {
        int n, d[2100328] = {1}, c[2100328] = {};
        vector<int> g[2100328] = {};
        bool b[22][22] = {};
        cin >> n;
        for (int i = 0; i < (1 << n); i++) for (int j = 0; j < n; j++) if (i & (1 << j)) g[i].push_back(j), c[i]++;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> b[i][j];
        for (int i = 0; i < n; i++) {
            for (int j = (int)(1 << n) - 1; j >= 0; j--) if (c[j] == i + 1) {
                for (int k : g[j]) if (b[i][k]) {
                    d[j] += d[j - (1 << k)];
                    if (d[j] >= mod) d[j] -= mod;
                }
            }
        }
        cout << d[(1 << n) - 1];
    }
};

class P {
public:
    vector<int> g[100005];
    ll d[100005], e[100005];
    
    void dfs(int x, int p) {
        d[x] = e[x] = 1;
        for (int i : g[x]) if (i != p) {
            dfs(i, x);
            d[x] = d[x] * e[i] % mod;
            e[x] = e[x] * (d[i] + e[i]) % mod;
        }
    }
    
    void solve() {
        int n, u, v;
        cin >> n;
        for (int i = 0; i < n - 1; i++) cin >> u >> v, g[u].push_back(v), g[v].push_back(u);
        dfs(1, 1);
        cout << (d[1] + e[1]) % mod;
    }
};

class Q {
public:
    void solve() {
        int n, h[200005] = {};
        ll t[200005] = {}, a[200005] = {}, y = 0;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> h[i];
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) {
            ll z = 0;
            for (int j = h[i]; j; j -= j & -j) z = max(z, t[j]);
            for (int j = h[i]; j <= n; j += j & -j) t[j] = max(t[j], z + a[i]);
        }
        for (int i = 1; i <= n; i++) y = max(y, t[i]);
        cout << y;
    }
};

class R {
public:
    vector<vector<ll>> mul(int n, vector<vector<ll>> c, vector<vector<ll>> d) {
        vector<vector<ll>> e(n);
        for (int i = 0; i < n; i++) e[i].resize(n);
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) e[i][j] = (e[i][j] + c[i][k] * d[k][j]) % mod;
        }
        return e;
    }
    
    void solve() {
        int n;
        vector<vector<ll>> a, b;
        ll m, z = 0;
        cin >> n >> m;
        a.resize(n); b.resize(n);
        for (int i = 0; i < n; i++) a[i].resize(n), b[i].resize(n);
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> a[i][j];
        for (int i = 0; i < n; i++) b[i][i] = 1;
        while (m) {
            if (m & 1) b = mul(n, b, a);
            a = mul(n, a, a);
            m >>= 1;
        }
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) z += b[i][j];
        cout << z % mod;
    }
};

class S {
public:
    void solve() {
        string k;
        int m;
        ll d[10004][102][2] = {};
        d[0][0][1] = 1;
        cin >> k >> m;
        for (int i = 1; i <= k.length(); i++) {
            for (int j = 0; j < m; j++) {
                for (int l = 0; l < 10; l++) d[i][(j + l) % m][0] += d[i - 1][j][0];
                for (int l = 0; l < k[i - 1] - '0'; l++) d[i][(j + l) % m][0] += d[i - 1][j][1];
                d[i][(j + k[i - 1] - '0') % m][1] = d[i - 1][j][1];
            }
            for (int j = 0; j < m; j++) d[i][j][0] %= mod;
        }
        cout << (d[k.length()][0][0] + d[k.length()][0][1] + mod - 1) % mod;
    }
};

class T {
public:
    void solve() {
        int n, d[3003][3003];
        string s;
        cin >> n >> s;
        for (int i = 1; i <= n; i++) d[1][i] = 1;
        for (int i = 2; i <= n; i++) {
            if (s[i - 2] == '<')
                for (int j = 1; j <= n - i + 1; j++)
                    d[i][j] = (d[i][j - 1] + d[i - 1][j]) % mod;
            else
                for (int j = n - i + 1; j; j--)
                    d[i][j] = (d[i][j + 1] + d[i - 1][j + 1]) % mod;
        }
        cout << d[n][1] << '\n';
    }
};

class U {
public:
    void solve() {
        int n;
        ll a[17][17] = {}, d[65541] = {}, s[65541] = {}, z = 0;
        cin >> n;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> a[i][j];
        for (int i = 0; i < (1 << n); i++) for (int j = 0; j < n; j++) for (int k = 0; k < j; k++) if (i & (1 << j) && i & (1 << k)) s[i] += a[j][k];
        for (int i = 0; i < (1 << n); i++) {
            vector<int> b;
            for (int j = 0; j < n; j++) if (i & (1 << j)) b.push_back(1 << j);
            int m = (int)b.size();
            for (int j = 0; j < (1 << m); j++) {
                int c = 0;
                for (int k = 0; k < m; k++) if (j & (1 << k)) c += b[k];
                d[i] = max(d[i], d[i - c] + s[c]);
            }
        }
        for (int i = 0; i < (1 << n); i++) z = max(z, d[i]);
        cout << z;
    }
};

class V {
public:
    int p[100005];
    ll d2[100005] = {1}, z[100005], m;
    vector<int> g[100005];
     
    void dfs(int x, int w) {
        d2[x] = 1;
        for (int i : g[x]) if (i != w) p[i] = x, dfs(i, x), d2[x] = d2[x] * (d2[i] + 1) % m;
        if (x > 1) g[x].erase(find(g[x].begin(), g[x].end(), w));
    }
 
    void dfs2(int x) {
        vector<ll> a = {1}, b = {1};
        for (int i = (int)g[x].size() - 1; i >= 0; i--) a.push_back(a.back() * (d2[g[x][i]] + 1) % m);
        for (int i = 0; i < g[x].size(); i++) b.push_back(b.back() * (d2[g[x][i]] + 1) % m);
        reverse(a.begin(), a.end());
        z[x] = d2[x];
        for (int i = 0; i < g[x].size(); i++) {
            d2[x] = d2[p[x]] * (b[i] * a[i + 1] % m) % m + 1;
            d2[g[x][i]] = d2[g[x][i]] * d2[x] % m;
        }
        for (int i = 0; i < g[x].size(); i++) d2[x] = d2[p[x]] * (b[i] * a[i + 1] % m) % m + 1, dfs2(g[x][i]);
    }
    
    void solve() {
        int n, u, v;
        cin >> n >> m;
        for (int i = 1; i < n; i++) cin >> u >> v, g[u].push_back(v), g[v].push_back(u);
        dfs(1, 1);
        dfs2(1);
        for (int i = 1; i <= n; i++) cout << z[i] << '\n';
    }
};

class W {
public:
    int n;
    ll t[400005], d1[200005];
    
    void apply(int p, ll v) {
        t[p] += v;
        if (p < n) d1[p] += v;
    }
    
    void build(int p) {
        while (p) p >>= 1, t[p] = max(t[p << 1], t[p << 1 | 1]) + d1[p];
    }
    
    void push(int p) {
        for (int s = 17; s; s--) {
            int i = p >> s;
            if (d1[i]) {
                apply(i << 1, d1[i]);
                apply(i << 1 | 1, d1[i]);
                d1[i] = 0;
            }
        }
    }
    
    void inc(int l, int r, ll v) {
        l += n, r += n;
        int l0 = l, r0 = r;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) apply(l++, v);
            if (r & 1) apply(--r, v);
        }
        build(l0);
        build(r0 - 1);
    }
    
    ll que(int l, int r) {
        ll z = -(ll)mod * mod;
        l += n, r += n;
        push(l);
        push(r - 1);
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) z = max(z, t[l++]);
            if (r & 1) z = max(z, t[--r]);
        }
        return z;
    }
    
    void solve() {
        int m, o, l[200005] = {}, r[200005] = {}, a[200005] = {};
        ll s = 0, z = 0;
        cin >> n >> m;
        for (int i = 0; i < m; i++) cin >> l[i] >> r[i] >> a[i], l[i]--;
        vector<pii> b[200005] = {}, c[200005] = {};
        for (int i = 0; i < m; i++) b[l[i]].push_back({r[i], a[i]}), c[r[i]].push_back({l[i], a[i]});
        for (int i = 0; i < n; i++) {
            for (pii j : b[i]) s += j.second;
            for (pii j : c[i]) s -= j.second;
            for (pii j : b[i]) inc(i, j.first, -j.second);
            for (pii j : c[i]) inc(j.first, i, j.second);
            z = max(z, max(0ll, que(0, i)) + s);
            inc(i, i + 1, max(0ll, que(0, i)) + s);
        }
        cout << z;
    }
};

class X {
public:
    void solve() {
        int n;
        ll z = 0, d[20004] = {};
        pair<pii, int> a[1003] = {};
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i].first.second >> a[i].first.first >> a[i].second, a[i].first.first += a[i].first.second;
        sort(a, a + n);
        for (int i = 0; i < n; i++) for (int j = a[i].first.first; j >= a[i].first.second; j--) d[j] = max(d[j], d[j - a[i].first.second] + a[i].second);
        for (int i = 0; i < 20003; i++) z = max(z, d[i]);
        cout << z;
    }
};

class Y {
public:
    void solve() {
        ll f[200005] = {1}, g[200005] = {}; g[200000] = 750007460;
        for (int i = 1; i <= 200000; i++) f[i] = f[i - 1] * i % mod;
        for (int i = 200000; i; i--) g[i - 1] = g[i] * i % mod;
        int h, w, n;
        ll d[3003] = {};
        pii a[3003] = {};
        cin >> h >> w >> n;
        a[n].first = h, a[n].second = w;
        for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
        sort(a, a + n);
        for (int i = 0; i <= n; i++) d[i] = f[a[i].first + a[i].second - 2] * g[a[i].first - 1] % mod * g[a[i].second - 1] % mod;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < i; j++) if (a[i].first >= a[j].first && a[i].second >= a[j].second) {
                d[i] -= d[j] * f[a[i].first - a[j].first + a[i].second - a[j].second] % mod * g[a[i].first - a[j].first] % mod * g[a[i].second - a[j].second] % mod;
                if (d[i] < 0) d[i] += mod;
            }
        }
        cout << d[n];
    }
};

class Z {
public:
      struct Line {
        ll k, m;
        mutable ll p;
        bool operator<(const Line& o) const {
            return k < o.k;
        }
        bool operator<(const ll&x) const {
            return p < x;
        }
    };
     
    struct LineContainer : multiset<Line, less<>> {
        // (for doubles, use inf = 1/.0, div(a,b) = a/b)
        const ll inf = numeric_limits<ll>::max();
        ll div(ll a, ll b) { // floored division
            return a / b - ((a ^ b) < 0 && a % b);
        }
        bool isect(iterator x, iterator y) {
            if (y == end()) { x->p = inf; return false; }
            if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
            else x->p = div(y->m - x->m, x->k - y->k);
            return x->p >= y->p;
        }
        void add(ll k, ll m) {
            auto z = insert({k, m, 0}), y = z++, x = y;
            while (isect(y, z)) z = erase(z);
            if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
            while ((y = x) != begin() && (--x)->p >= y->p)
                isect(x, erase(y));
        }
        ll query(ll x) {
            assert(!empty());
            auto l = *lower_bound(x);
            return l.k * x + l.m;
        }
    };

    void solve() {
        ll c, a[200005] = {};
        int n;
        cin >> n >> c;
        for (int i = 0; i < n; i++) cin >> a[i];
        LineContainer lc;
        lc.add(0, 0);
        ll f = 0;
        for(int i = 0; i < n; i++){
            f = lc.query(a[i]);
            f -= a[i] * a[i] + c;
            if (!i) f = 0;
            lc.add(a[i] + a[i], -a[i] * a[i] + f);
        }
        cout << -f;
    }
};

int main() {
    ios::sync_with_stdio(false);
    Z problem;
    problem.solve();
}


Measured memory_bytes: 17588