#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
#define sz(s) (int)s.size()
#define mem(a,i) memset(a,i,sizeof(a))
#define pb push_back
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define ll long long
#define F first
#define S second
#define ld long double
#define ppb pop_back
const int MAX=2e5+10;
const ll inf=1e16;
vector<int> vec[MAX];
vector<vector<ll>> dp;
int n,m,k;
ll S(int x,int y){
ll a=x-y+1;
if(a<=0)return 0;
return a*a;
}
ld inter(pair<ll,ll> a,pair<ll,ll> b){
return (a.S-b.S)/(b.F-a.F);
}
struct cht{
vector<pair<ll,ll>> lines;
int pos;
void init(){
lines.clear();
pos=0;
}
void add(ll k,ll x){
while(sz(lines)>1&&inter(lines[sz(lines)-2],lines.back())>inter(lines[sz(lines)-2],{k,x}))lines.ppb();
lines.pb({k,x});
pos=min(pos,sz(lines)-1);
}
ll get(pair<ll,ll> a,ll x){
return a.F*x+a.S;
}
ll get(ll x){
if(lines.empty()){
return inf;
}
while(pos+1<sz(lines)&&get(lines[pos],x)>get(lines[pos+1],x)){
pos++;
}
return get(lines[pos],x);
}
}C;
long long take_photos(int N, int M, int K, vector<int> r, vector<int> c) {
n=N,m=M,k=K;
vector<int> actr,actc;
for(int i=0;i<n;i++){
if(c[i]-r[i]>0){
swap(c[i],r[i]);
}
vec[r[i]].pb(c[i]);
}
for(int i=0;i<m;i++)sort(all(vec[i]));
stack<int> st;
for(int i=0;i<m;i++){
if(vec[i].empty())continue;
while(!st.empty()&&vec[st.top()][0]>=vec[i][0]){
st.pop();
}
st.push(i);
}
vector<pii> pts;
while(!st.empty()){
int x=st.top();
pts.pb({x,vec[x][0]});
st.pop();
}
reverse(all(pts));
n=sz(pts);
dp.resize(n);
for(int i=0;i<n;i++){
dp[i].resize(k+1);
for(int j=0;j<=k;j++){
dp[i][j]=inf;
}
}
for(int i=0;i<n;i++){
dp[i][1]=S(pts[i].F,pts[0].S);
if(i!=n-1){
dp[i][1]+=S(pts[i].F,pts[i+1].S);
}
}
// cerr<<"OK\n";
for(int j=2;j<=k;j++){
C.init();
// cerr<<j<<"\n";
for(int i=0;i<n;i++){
if(i-1>=0)C.add(-2*pts[i].S,dp[i-1][j-1]+pts[i].S*pts[i].S-2*pts[i].S);
else C.add(-2*pts[i].S,+pts[i].S*pts[i].S-2*pts[i].S);
dp[i][j]=C.get(pts[i].F)+pts[i].F*pts[i].F+2*pts[i].F+1;
if(i!=n-1){
dp[i][j]+=S(pts[i].F,pts[i+1].S);
}
dp[i][j]=min(dp[i][j],inf);
// cout<<i<<" "<<j<<" "<<dp[i][j]<<"\n";
}
}
ll ans=inf;
for(int j=1;j<=k;j++)ans=min(ans,dp[n-1][j]);
return ans;
}
