#include #include #include #include #include #include #include #include #include #include #include #define mk make_pair #define pb push_back #define printf printf_s #define scanf scanf_s using namespace std; typedef long long int ll; typedef pair pos; const ll MOD = 1000000007, N = 200001, dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }, MIN = -72340172838, MAX = 72340172838; ll mn(ll a, ll b) { if (a == -1)return b; if (b == -1)return a; return min(a, b); } ll gcd(ll v1, ll v2) { if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2); } ll pw(ll v1, ll v2) { ll v3 = 1; while (v2 > 0) { if (v2 % 2)v3 = (v3*v1) % MOD; v1 = (v1*v1) % MOD; v2 /= 2; } return v3; } struct ab { ll a, b; bool operator<(const ab& right) const { return right.b*a - right.a*b < 0; } }; ll n, k, mx, mnv, ans = 0; pos pr[N]; queue ql; bool ok(ll md) { ll bt = MIN; for (int i = 0; i < n; i++) { if (pr[i].second <= md)continue; if (pr[i].first - bt < k)return false; bt = pr[i].first; } return true; } int main() { cin >> n >> k; for (int i = 0; i < n; i++) { cin >> pr[i].first >> pr[i].second; mx = max(mx, pr[i].second); ans += pr[i].second; } if (ok(0)) { cout << 0 << endl << 0 << endl; return 0; } while (mx - mnv > 1) { ll md = (mx + mnv) / 2; if (ok(md))mx = md; else mnv = md; } cout << mx << endl; for (int i = 0; i < n; i++) { if (pr[i].second > mx) { ql.push(pr[i].first); ans -= pr[i].second; } } ql.push(MAX); ll dp[N] = {}, mxv[N] = {},lt=MIN,bt=-1; for (int i = 0; i < n; i++) { while (ql.front() < pr[i].first) { lt = ql.front(); ql.pop(); } if (pr[i].first - lt >= k && ql.front() -pr[i].first >= k) { while (pr[i].first - pr[bt + 1].first>=k)bt++; ll btv = 0; if (bt != -1)btv = mxv[bt]; dp[i] = btv + pr[i].second; } if (i != 0)mxv[i] = max(dp[i], mxv[i - 1]); else mxv[i] = dp[i]; } cout << ans - mxv[n - 1] << endl; return 0; }