#include "bits/stdc++.h"
#define ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;
const ll INF = 1e18;
vector<ll> dp,ndp;
vector<array<ll,2>> v;
void f(ll l,ll r,ll optl,ll optr){
if(l>r) return;
ll mid = (l+r)/2;
ll cur = INF, best = -1;
for(int i = min(mid,optr) ; i >= max(1LL,optl) ; i--){
ll b = v[mid][1];
ll a = v[i][0];
ll d = (i > 1 ? v[i - 1][1] : 0);
if(dp[i-1] + (b-a) * (b-a) + max(0LL,d-a) * max(0LL,d-a) < cur){
best = i;
cur = dp[i-1] + (b-a) * (b-a) + max(0LL,d-a) * max(0LL,d-a);
}
}
ndp[mid] = cur;
f(l,mid-1,optl,best) , f(mid+1,r,best,optr);
}
ll take_photos(int n,int m,int k,vector<int> r,vector<int> c){
for(int i=0;i<n;i++){
ll a=r[i],b=c[i];
if(a>b) swap(a,b);
v.push_back({a,b});
}
sort(all(v));
vector<array<ll,2>> xdd;
xdd.push_back({-1LL,-1LL});
for(int i=0;i<n;i++) if(xdd.back()[1] < v[i][1]) xdd.push_back(v[i]);
swap(v,xdd);
n = sz(v) - 1;
dp.assign(n+5,INF);
dp[0] = 0;
for(int i=1;i<=k;i++){
ndp.assign(n+5,INF);
f(1,n,1,n);
swap(dp,ndp);
}
return dp[n];
}
/*void _(){
int n,m,k;
cin >> n >> m >> k;
for(int i=0;i<n;i++){
int a,b;
cin >> a >> b;
if(a>b) swap(a,b);
v.push_back({a,b});
}
sort(all(v));
vector<array<int,2>> xdd;
xdd.push_back({-1,-1});
for(int i=0;i<n;i++) if(xdd.back()[1] < v[i][1]) xdd.push_back(v[i]);
swap(v,xdd);
n = sz(v) - 1;
dp.assign(n+5,INF);
dp[0] = 0;
for(int i=1;i<=k;i++){
ndp.assign(n+5,INF);
f(1,n,1,n);
swap(dp,ndp);
}
cout << dp[n] << '\n';
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/
