#include using namespace std; using ll = long long; using pii = pair; template using V = vector; template using VV = V>; #define pb push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define rep(i, n) rep2(i, 0, n) #define rep2(i, m, n) for (int i = m; i < (n); i++) #define per(i, b) per2(i, 0, b) #define per2(i, a, b) for (int i = int(b) - 1; i >= int(a); i--) #define ALL(c) (c).begin(), (c).end() #define SZ(x) ((int)(x).size()) constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); } template void chmin(T& t, const U& u) { if (t > u) t = u; } template void chmax(T& t, const U& u) { if (t < u) t = u; } template ostream& operator<<(ostream& os, const pair& p) { os << "(" << p.first << "," << p.second << ")"; return os; } template ostream& operator<<(ostream& os, const vector& v) { os << "{"; rep(i, v.size()) { if (i) os << ","; os << v[i]; } os << "}"; return os; } #ifdef LOCAL void debug_out() { cerr << endl; } template void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...); } #define debug(...) \ cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl #else #define debug(...) (void(0)) #define dump(x) (void(0)) #endif // modified // https://github.com/kth-competitive-programming/kactl/blob/master/content/data-structures/LineContainer.h // lines : y = kx + m // find maximum at x struct Line { mutable ll k, m, p; bool operator<(const Line& o) const { return k < o.k; } bool operator<(ll x) const { return p < x; } }; template struct LineContainer : multiset> { // (for doubles, use inf = 1/.0, div(a,b) = a/b) static const ll inf = LLONG_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()) return x->p = inf, 0; 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) { if (!maximum) k = -k, m = -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); auto res = l.k * x + l.m; if (!maximum) res = -res; return res; } }; const ll INF = TEN(18); int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N; ll C; cin >> N >> C; V a(N), b(N); rep(i, N) cin >> a[i] >> b[i]; V dp(N + 1, INF), sub(N + 1, INF); dp[0] = 0; LineContainer ls, ld; rep(i, N) { ls.add(-i, C * i * i + dp[i] * 2); sub[i + 1] = ls.query((2 * i + 1) * C + 2 * a[i]); if (i) { ld.add(-i * C + a[i - 1], -(i - 1) * a[i - 1] + C * i * (i - 3) / 2 + sub[i]); dp[i + 1] = ld.query(i) + C * (i + 1) * (i + 2) / 2; } sub[i + 1] = sub[i + 1] / 2 + b[i] + a[i] * (i + 1) + C * i * (i + 1) / 2; chmin(dp[i + 1], sub[i + 1]); } debug(dp); debug(sub); cout << dp[N] << endl; return 0; }