令 \(f_i\) 为当 \(k=i\) 时的答案。令 \(g_i\) 为 \(f_i+\max\limits_{j\in S} b_j\)。也就是不减去 \(b\) 的最大值的结果。
直接做是 \(O(n^2)\) 的，考虑分治，令两个子问题的 \(f,g\) 分别为 \(fl,gl\) 和 \(fr, gr\)。
合并的时候做一个
\[f_i=\max(\max\limits_{c+d=i}(gl_c+fr_d),\max(fl_i,fr_i)) \]\[g_i=\max\limits_{j+k=i}(gl_j+gr_k) \]即可。
但是 \((\max,+)\) 卷积怎么做？
对于 \(g\)，因为递归到最小的子问题时，得到的 \(g\) 是上凸函数，所以合并后的 \(g\) 仍然是上凸的，直接闵可夫斯基和就做完了。
对于 \(f\)，\(f\) 并不是凸的，但是 \(g\) 是凸的，考虑是否有决策单调性。结论是：有。
设 \(p_i\) 为 \(f_i\) 的决策点，即 \(f_i=fr_{p_i} + gl_{i - p_i}\)。
令 \(w(a,b)=gl_{b-a}\)。
接下来证明 \(w(a-1,b+1)+w(a,b)\le w(a-1,b)+w(a,b+1)\)。
设 \(x=b-a+1\)。
则变为证明 \(g_{x+1}+g_{x-1}\le 2\times g_x\)。
设 \(k_x=g_{x+1}-g_x\)。因为 \(g\) 上凸，所以 \(k_x\) 单调不增。
所以 \(g_{x+1}+g_{x-1}=2\times g_{x-1} + k_{x-1}+k_x,2\times g_x=2\times g_{x-1}+2\times k_{x-1}\)。
因为 \(k_x\le k_{x-1}\)，所以原式成立。
接下来证明 \(p_i\) 单调。考虑反证法：
若存在大于 \(i\) 的 \(c\) 使得 \(p_c<p_i\)，则有：
\[f_c=fl_{p_c} + w(p_c,c)\\ f_i=fl_{p_i} + w(p_i,i) \]那么 \(f_i+f_c=fl_{p_c} + w(p_c,c)+fl_{p_i} + w(p_i,i)\)。
根据四边形不等式，因为 \(p_c<p_i,c>i\)，所以 \(w(p_c,c)+w(p_i,i)\le w(p_c,i)+w(p_i,c)\)。
所以有 \(f_c+f_i\le fl_{p_c} + w(p_c,i)+fl_{p_i} + w(p_i,c)\)。但又有 \(fl_{p_c}+w(p_c,i)\le f_i,fl_{p_i}+w(p_i,c)\le f_i\)，也就是说当且仅当四边形不等式取等时成立，这时只令 \(p_c=p_i\) 即可。
所以有决策单调性，简单的二分队列优化一下 dp 就行了。常数小跑得飞快。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const ll inf = 1e18;
int n;
struct node {ll a, b;} a[N];
pair<vector<ll>, vector<ll>> solve(int l, int r)
{
if(l > r) return {{}, {0}};
if(l == r) return {{a[l].a}, {0, a[l].a - a[l].b}};
int mid = l + r >> 1;
int len = r - l + 1;
auto L = solve(l, mid);
auto R = solve(mid + 1, r);
vector<ll> &fr = R.second;
vector<ll> &gl = L.first;
vector<ll> f(len + 1, 0);
vector<ll> g(len);
merge(gl.begin(), gl.end(), R.first.begin(), R.first.end(), g.begin(), greater<ll>());
for(int i = 1; i < gl.size(); i ++) gl[i] += gl[i - 1];
gl.insert(gl.begin(), 0);
struct node {int l, r, v;};
deque<node> q; q.push_back({1, len, 1});
auto calc = [&](int pos, int v) {if(pos - v >= gl.size()) return -inf; return fr[v] + gl[pos - v];};
for(int i = 1; i < fr.size(); i ++)
{
f[i] = calc(i, q.front().v);
q.front().l ++;
if(q.front().l > q.front().r) q.pop_front();
while(q.size() && calc(q.back().l, q.back().v) <= calc(q.back().l, i)) q.pop_back();
int pl = n + 1;
if(q.size())
{
int L = q.back().l, R = q.back().r + 1, nowv = q.back().v;
while(L < R)
{
int mid = L + R >> 1;
if(calc(mid, i) < calc(mid, nowv)) L = mid + 1;
else R = mid;
}
q.back().r = R - 1;
if(q.back().l > q.back().r) q.pop_back();
pl = R;
}
else pl = i + 1;
if(pl <= len) q.push_back({pl, len, i});
}
for(auto [l, r, v] : q)
for(int i = l; i <= r; i ++)
f[i] = calc(i, v);
for(int i = 1; i < L.second.size(); i ++) f[i] = max(f[i], L.second[i]);
for(int i = 1; i < R.second.size(); i ++) f[i] = max(f[i], R.second[i]);
return {g, f};
}
const int maxn = (1 << 22) + 5;
char buf[maxn], *S = buf, *T = buf;
char gc() {return (S == T) ? (T = (S = buf) + fread(buf, 1, maxn, stdin), (S == T) ? EOF : *S ++) : (*S ++);}
template<typename T>
void read(T &x)
{
x = 0; char c = gc(); bool f = 0;
while(c < '0' || c > '9') f |= c == '-', c = gc();
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc();
if(f) x = -x;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
read(n);
for(int i = 1; i <= n; i ++) read(a[i].a), read(a[i].b);
sort(a + 1, a + n + 1, [](node &x, node &y) {return x.b < y.b;});
vector<ll> ans = solve(1, n).second;
for(int i = 1; i <= n; i ++)
cout << ans[i] << "\n";
return 0;
}