悬赏一个关注。大概是每个包错了几个点。

#include<bits/stdc++.h>
using namespace std;
#define inf 1e15
#define ll long long
const double eps=1e-10;
const int maxn=2e5+10;
const int mod=1e9+7;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
struct node{int l,r;}b[maxn],a[maxn];int n,m,q[maxn],c[maxn];
ll v[maxn],g[maxn],ans=inf,f[maxn];
inline int cmp(node x,node y){return x.l==y.l?x.r>y.r:x.l<y.l;}
inline ll X(int x){return a[x+1].l;}
inline ll Y(int x){return f[x]+g[x];}
inline double slope(int x,int y){return 1.0*(Y(y)-Y(x))/(X(y)-X(x));}
inline int check(ll k){
	int l,r;q[l=r=1]=0;
	for(int i=1;i<=n;i++){
		while(l<r&&2*a[i].r>=slope(q[l],q[l+1]))l++;c[i]=c[q[l]]+1;
		f[i]=f[q[l]]+1ll*(a[i].r-a[q[l]+1].l+1)*(a[i].r-a[q[l]+1].l+1)-v[q[l]]+k;
		//printf("%lld %d\n",f[i],q[l]);
		while(l<r&&slope(q[r],i)<=slope(q[r-1],q[r]))r--;q[++r]=i;
	}if(c[n]<=m)ans=f[n]-k*c[n];return c[n];
}
int main(){
	n=read(),read(),m=read();
	for(int i=1;i<=n;i++){
		b[i].l=read(),b[i].r=read();
		if(b[i].l>b[i].r)swap(b[i].l,b[i].r);
	}sort(b+1,b+1+n,cmp);int top=0;
	for(int i=1;i<=n;i++)
		if(!top||b[i].r>a[top].r)a[++top]=b[i];
	n=top;//printf("n=%d\n",n);
	//for(int i=1;i<=n;i++)
	//	printf("%d %d\n",a[i].l,a[i].r);
	for(int i=1;i<n;i++)v[i]=max(0,a[i].r-a[i+1].l+1);
	for(int i=1;i<n;i++){
		v[i]=1ll*v[i]*v[i];
		g[i]=1ll*a[i+1].l*a[i+1].l-2ll*a[i+1].l-v[i];
	}ll l=0,r=1e12;
	while(l<=r){
		ll mid=(l+r)>>1;
		if(check(mid)<=m)r=mid-1;
		else l=mid+1;
	}printf("%lld\n",ans);
    return 0;
}