思路是二分+三分：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, inf = 1e9;
int n, k, a[N], b[N]; 
int cntx(int p, int x) {
	int sum = 0;
	for(int i = 1;i <= n; ++i) 
		if(a[i] < x or a[i] > x + p) sum += min(abs(x + p - a[i]), abs(x - a[i]));
	return sum;
} 
int cnty(int p, int x) {
	int sum = 0;
	for(int i = 1;i <= n; ++i) 
		if(b[i] < x or b[i] > x + p) sum += min(abs(x + p - b[i]), abs(x - b[i]));
	return sum;
}   
int getx(int x) { // 边长 
	int l = 0, r = inf;
	while(l + 2 < r) { // 边长 
		int lmid = l + (r - l) / 3, rmid = r - (r - l) / 3; 
		if(cntx(x, lmid) < cntx(x, rmid)) r = rmid;
		else l = lmid; //cout << "x::" << l << " " << r << "\n";
	} 
//	cout << x << " " << l << "---- x\n";
	return min({cntx(x, l), cntx(x, l + 1), cntx(x, l + 2)});
}
int gety(int x) {
	int l = 0, r = inf;
	while(l + 2 < r) { // 边长 
		int lmid = l + (r - l) / 3, rmid = r - (r - l) / 3; 
		if(cnty(x, lmid) < cnty(x, rmid)) r = rmid;
		else l = lmid; //cout << "y::" << l << " " << r << "\n";
	} 
//	cout << x << " " << l << "---- y\n";
	return min({cnty(x, l), cnty(x, l + 1), cnty(x, l + 2)});
}
signed main() {
	cin >> n >> k;
	for(int i = 1;i <= n; ++i) {
		cin >> a[i] >> b[i];
	}
//	cout << cntx(3, 1) << " " << cnty(3, 1) << "\n"; return 0;
	int l = 0, r = inf;
	while(l < r) {
		int mid = l + r >> 1;
		if(getx(mid) + gety(mid) <= k) r = mid;
		else l = mid + 1;
	} cout << l;
	return 0;
}
/*
考虑二分答案

正方形确定 ：(x, y) & a 

二分 x & a： 相当于已经确定了 [x,x + a - 1] 列，贪心地向最中间走 
  
三分这个 a 
  
然后分别三分 x 和 y  
  
我们把 x 移动和 y 移动拆开，x 的移动在三分中计算，y 的移动直接提前三分计算？  

*/