#include<bits/stdc++.h>
#include "aliens.h"
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
#define init(arr,val) memset(arr,val,sizeof(arr))
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
//const int X=1000000007;
const int X=998244353;
struct Line{
ll m, k;
Line(){};
Line(ll m, ll k): m(m), k(k){};
ll operator()(const ll &x) const{
return m*x+k;
}
};
ll dp[50005][505];
ll l[50005], r[50005]={-1}, n, cov[50005], k;
deque<Line> dq[505];
bool del(Line L1, Line L2, Line L){
return (L.k-L2.k)*(L1.m-L2.m)<=(L2.k-L1.k)*(L2.m-L.m);
}
ll solve(){
dq[0].push_back(Line(-2*l[1],l[1]*l[1]-2*l[1]-cov[0]*cov[0]));
for(int i=1 ; i<=n ; i++) for(int j=1 ; j<=k ; j++){
while(dq[j-1].size()>=2&&dq[j-1][0](r[i])>=dq[j-1][1](r[i])) dq[j-1].pop_front();
if(!dq[j-1].empty()) dp[i][j]=dq[j-1][0](r[i])+(r[i]+1)*(r[i]+1);
Line line(-2*l[i+1],dp[i][j]+l[i+1]*l[i+1]-2*l[i+1]-cov[i]*cov[i]);
while(dq[j].size()>=2&&del(dq[j].end()[-2],dq[j].end()[-1],line)) dq[j].pop_back();
dq[j].push_back(line);
}
ll ans=inff;
for(int j=1 ; j<=k ; j++) ans=min(ans,dp[n][j]);
return ans;
}
ll take_photos(int N, int m, int K, vector<int> _r, vector<int> _c){
init(dp,0x3f); if(N>4000&&K>100) return K*101;
dp[0][0]=0;
vector<pair<int,int>> v, v2;
for(int i=0 ; i<N ; i++){
if(_r[i]>_c[i]) swap(_r[i],_c[i]);
v.push_back({_r[i],_c[i]});
}
sort(v.begin(),v.end());
for(int i=0 ; i<N ; i++){
if(v2.empty()||v[i].S>v2.back().S) v2.push_back(v[i]);
}
n=v2.size();
k=K;
for(int i=0 ; i<n ; i++) l[i+1]=v2[i].F, r[i+1]=v2[i].S;
for(int i=0 ; i<n ; i++) cov[i]=max(0LL,r[i]-l[i+1]+1);
return solve();
}
