#include using namespace std; using ll = long long; template struct dual_segtree { public: dual_segtree() : dual_segtree(0) {} dual_segtree(int n) : dual_segtree(std::vector(n, id())) {} dual_segtree(const std::vector& v) : _n(int(v.size())) { log = ceil_pow2(_n); size = 1 << log; d = std::vector(2 * size, id()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; } const S& operator[](int p) const { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return d[p]; } S& operator[](int p) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return d[p]; } void apply(int p, S f) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = mapping(f, d[p]); } void apply(int l, int r, S f) { assert(0 <= l && l <= r && r <= _n); if (l == r) return; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } } private: int _n, size, log; std::vector d; void all_apply(int k, S f) { d[k] = mapping(f, d[k]); } void push(int k) { all_apply(2 * k, d[k]); all_apply(2 * k + 1, d[k]); d[k] = id(); } int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } }; using S = ll; //xにfを作用させた時の値の変化 S op(S f, S x){return max(x, f);} //作用させても変化させないもの S id(){return 0;} int main(){ ios::sync_with_stdio(false); cin.tie(0); int N, K, ng = -1, ok = 1 << 30, mid; cin >> N >> K; vector T(N + 2), D(N + 2); for(int i = 1; i <= N; i++) cin >> T[i] >> D[i]; T[0] = -K; T[N + 1] = T[N] + K; auto f = [&](int mid){ int pos = -K; for(int i = 0; i <= N; i++){ if(D[i] > mid){ if(T[i] < pos + K) return false; pos = T[i]; } } return true; }; while(ng + 1 < ok){ mid = (ok + ng) / 2; if(f(mid)) ok = mid; else ng = mid; } dual_segtree seg(N + 3); for(int l = 0, r1 = 0, r2 = 0, s = 0; l <= N; l++){ r1 = max(r1, l + 1); r2 = max(r2, l + 1); while(r1 <= N + 1 && T[r1] < T[l] + K) r1++; while(r2 <= N + 1 && D[r2] <= ok) r2++; if(r1 <= r2) seg.apply(r1, r2 + 1, seg[l] + D[l]); } cout << ok << '\n'; cout << accumulate(D.begin(), D.end(), 0ll) - seg[N + 2] << '\n'; }