#include #include using namespace std; using ll = long long; using S = pair; using F = int; //単位元 S e(){return make_pair(1 << 30, 1 << 30);} //演算 S op(S l,S r){return min(l, r);} //xにfを作用させた時の値の変化 S mapping(F f,S x){return make_pair(max(x.first, f), x.second);} //gを演算した後にfを演算させると演算子はどうなるか F composition(F f, F g){return max(f, g);} //作用させても変化させないもの F id(){return 0;} int main(){ ios::sync_with_stdio(false); cin.tie(0); int N, K; cin >> N >> K; vector T(N + 1), D(N + 1); for(int i = 1; i <= N; i++) cin >> T[i] >> D[i]; T[0] = -(1 << 30); atcoder::lazy_segtree seg(N + 1); seg.set(0, {0, 0}); ll s = accumulate(D.begin(), D.end(), 0ll); for(int i = 1, r = 0; i <= N; i++){ while(T[r] + K <= T[i]) r++; auto p = seg.prod(0, r); p.second -= D[i]; seg.set(i, p); seg.apply(0, i, D[i]); } auto p = seg.all_prod(); cout << p.first << '\n'; cout << s + p.second << '\n'; }