#include #include using namespace std; using namespace atcoder; typedef long long ll; typedef long double ld; #define REP(i, n) for (int i = 0; i < (n); ++i) #define REPR(i, n) for (int i = n - 1; i >= 0; --i) #define FOR(i, m, n) for (int i = m; i < n; ++i) #define FORR(i, m, n) for (int i = m; i >= n; --i) #define ALL(v) (v).begin(),(v).end() #define ALLR(v) (v).rbegin(),(v).rend() #define fi first #define se second #define PB push_back #define EB emplace_back template using PQ = priority_queue; template using QP = priority_queue,greater>; templatevoid debug(const T &v,ll h,ll w){for(ll i=0;ivoid debug(const T &v,ll n){for(ll i=0;ivoid debug(const vector&v){debug(v,v.size());} templatevoid debug(const vector>&v){for(auto &vv:v)debug(vv,vv.size());} templatevoid debug(stack st){while(!st.empty()){cerr<void debug(queue st){while(!st.empty()){cerr<void debug(deque st){while(!st.empty()){cerr<void debug(PQ st){while(!st.empty()){cerr<void debug(QP st){while(!st.empty()){cerr<void debug(const set&v){for(auto z:v)cerr<void debug(const multiset&v){for(auto z:v)cerr<void debug(const array &a){for(auto z:a)cerr<void debug(const map&v){for(auto z:v)cerr<<"["<void foo(Head&& head, Tail&&... tail){cerr << head << " ";foo(move(tail)...);} templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b> n >> k; vector t(n),d(n); REP(i,n) cin >> t[i] >> d[i]; ll ng=-1,ok=inf; while(ok-ng>1){ ll md=(ng+ok)/2; bool can=true; ll p=-inf; REP(i,n){ if(d[i]<=md) continue; if(p+k>t[i]) can=false; else p=t[i]; } (can?ok:ng)=md; } cout << ok << endl; ll sum=0; REP(i,n) if(d[i]<=ok) sum+=d[i]; vector imo(n+1); REP(i,n){ if(d[i]<=ok) continue; int l=upper_bound(ALL(t),t[i]-k)-t.begin(); int r=lower_bound(ALL(t),t[i]+k)-t.begin(); imo[l]++,imo[r]--; d[i]=0; } int tmp=0; REP(i,n){ tmp+=imo[i]; if(tmp>=1) d[i]=0; } vector dp(n+1); REP(i,n){ int r=lower_bound(ALL(t),t[i]+k)-t.begin(); chmax(dp[i+1],dp[i]); chmax(dp[r],dp[i]+d[i]); } // foo(sum); // debug(d); // debug(dp); cout << sum-dp[n] << endl; }