这个感觉很离谱啊，我不是很会这个。
考虑 DP。根据 THUSC 的经验，这个 \(K\) 和坐标一定不能设进状态，我们考虑把它放到转移里考虑。
对于一个盘子，如果我们接住了它，那就确定了它的坐标，而且我们知道两个盘子间的距离，这样就解决了坐标。
对于 \(K\)，我们考虑一个经典的 trick：分段转移。
发现可以互相到达的盘子是若干连续段，所以可以这样 DP：设 \(f_i\) 表示前 \(i\) 个盘子的最大贡献，那么 \(f_i=\max\limits_{j|j,i可以同时接住} \{(i-j+1)^2 + \max\limits_{k|k,j可以同时接住} f_k \}\)。
后面那个东西和 \(i\) 没关系，考虑把它设成 \(g_j\)。这样是 \(\mathcal O(n^2)\) 的。
在它这个状态转移上下功夫，我们发现 \(i,j(i\lt j)\) 可以同时接住的条件是 \(|a_i-a_j|\le b_j-b_i\)，转化一下就是 \(a_i-a_j\le b_j-b_i\) 且 \(a_j-a_i\le b_j-b_i\)，可以凑出一个相当漂亮的形式：\(a_i+b_i\le a_j+b_j, b_i-a_i\le b_j-a_j\)。
那么把 \((a_i + b_i, b_i - a_i)\) 看作平面上的点，这就是一个二维偏序问题，BIT 维护最大值即可。这样就解决了 \(g\) 的问题。
然后考虑 \(f\)，这个平方的式子是一个经典的斜率优化的形式，用栈维护一个上凸包，在上面二分即可。
注意我们这个转移时基于 \(j\) 可以到达 \(i\) 的，这样划分为了若干连续段，所以我们对每个连续段都要单独开一个栈维护凸包。
关于 \(g\) 和 \(f\) 的互相影响，我们下意识地使用半在线的方法计算。但这是不必要的！观察到 \(i\to j\) 的连续段，\(a+b,b-a\) 一定都是单增的，所以 \(g\) 的转移顺序并不会受 \(f\) 的转系顺序影响，直接在一开始按 \(a+b\) 拍个序做就行了。
时间复杂度 \(\mathcal O(n\log n)\)。
Typora Github Theme 的代码块渲染怎么这么奇怪。这么不牛。
#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second
const int maxn = 5e5 + 5;
const long double eps = 1e-6;
using i64 = long long;
using ld = long double;
struct node {
int x, y, id;
node() {
x = y = id = 0;
}
node(int x, int y, int id) : x(x), y(y), id(id) {}
} s[maxn];
int n, cnt, bel[maxn];
i64 c[maxn], f[maxn], g[maxn];
void chkmax(i64& x, i64 y) {
if(y > x)
x = y;
return ;
}
int lowbit(int x) {
return x & -x;
}
void add(int x, i64 y) {
for(;x <= cnt;x += lowbit(x))
chkmax(c[x], y);
return ;
}
i64 query(int x) {
i64 ans = 0;
for(;x;x -= lowbit(x))
chkmax(ans, c[x]);
return ans;
}
i64 calc(int x) {
return g[x] + 1ll * x * x - 2 * x;
}
ld slope(int x, int y) {
return 1.0 * (calc(y) - calc(x)) / (y - x);
}
struct Stack {
std::vector<int> q;
void insert(int x) {
while(q.size() > 1&&slope(q[q.size() - 2], q.back()) - slope(q.back(), x) <= -eps)
q.pop_back();
q.pb(x);
return ;
}
int query(int x) {
if(q.size() == 1)
return q.back();
int l = 0, r = q.size() - 2;
while(l <= r) {
int mid = (l + r) >> 1;
if(slope(q[mid], q[mid + 1]) - 2.0 * x >= eps)
l = mid + 1;
else
r = mid - 1;
}
return q[l];
}
} stk[maxn];
int main() {
scanf("%d", &n);
for(int i = 1;i <= n;++ i) {
int a, b;
scanf("%d %d", &a, &b);
c[++ cnt] = b - a;
s[i] = node(a + b, b - a, i);
bel[i] = bel[i - 1] + (s[i].x < s[i - 1].x||s[i].y < s[i - 1].y);
}
std::sort(c + 1, c + 1 + cnt);
cnt = std::unique(c + 1, c + 1 + cnt) - c - 1;
for(int i = 1;i <= n;++ i)
s[i].y = std::lower_bound(c + 1, c + 1 + cnt, s[i].y) - c;
for(int i = 1;i <= cnt;++ i)
c[i] = 0;
std::sort(s + 1, s + 1 + n, [&](const node& lhs, const node& rhs) {
return (lhs.x ^ rhs.x) ? (lhs.x < rhs.x) : (lhs.y < rhs.y);
});
for(int i = 1;i <= n;++ i) {
int x = s[i].id;
g[x] = query(s[i].y);
stk[bel[x]].insert(x);
int p = stk[bel[x]].query(x);
f[x] = g[p] + 1ll * (x - p + 1) * (x - p + 1);
add(s[i].y, f[x]);
}
i64 ans = 0;
for(int i = 1;i <= n;++ i)
chkmax(ans, f[i]);
printf("%lld\n", ans);
return 0;
}