#include "aliens.h"
#include<bits/stdc++.h>
#define int long long
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define dout(x); cout<<x<<' '<<#x<<endl;
#define dout2(x,y); cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
#define vout(v); for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;
vi psb; vi a, b; vpii v; vvi dp;
int intersect(pii &a, pii &b){
if(a.S<b.F)return 0; else return a.S-b.F+1;
}
int sq(int x){
return x * x;
}
int area(int x, int y){
return a[x] + (psb[y+1]-psb[x+1]);
}
int C(int x, int y){
return (v[y].S - v[x].F + 1) * (v[y].S - v[x].F + 1) - area(x,y);
}
void solve(int j, int l, int r, int cl, int cr){
if(l>r)return; int mid = l + r >> 1; int mn = 1e18, mnd = -1;
FOR(i,cl,min(mid,cr)+1){
if(mn > dp[i-1][j-1] + C(i,mid))mn = dp[i-1][j-1] + C(i,mid), mnd = i;
}
dp[mid][j] = mn; solve(j,l,mid-1,cl,mnd); solve(j,mid+1,r,mnd,cr);
}
long long take_photos(signed n, signed m, signed k, std::vector<signed> r, std::vector<signed> c) {
vi p(m,-1); f0r(i,n){
int x = r[i], y = c[i]; if(x > y)swap(x,y); p[x] = max(p[x], y);
// FOR(a,x,y+1)FOR(b,x,y+1)grid[a][b] = 1;
}
int mx = -1; f0r(i,m){
if(p[i] > mx){
mx=p[i]; v.pb(mp(i,p[i]));
}
} n = v.size(); b.pb(0); //for(auto u : v)cout<<u.F<<' '<<u.S<<'\n';
f0r(i,v.size()){
a.pb((v[i].S-v[i].F+1)*(v[i].S-v[i].F+1));
if(i!=0)b.pb(a[i] - intersect(v[i-1],v[i]) * intersect(v[i-1],v[i]));
}
psb.resize(n+1); FOR(i,1,n+1)psb[i]=psb[i-1]+b[i-1];
int sum = area(0,n-1); dp.resize(n); f0r(i,n)dp[i].resize(k+1,1e18);
f0r(i,n)dp[i][1] = C(0,i);
FOR(j,2,k+1){
solve(j,j-1,n-1,j-1,n-1);
}
int ans = 4e18; f0r(i,k+1)ans = min(ans, dp[n-1][i]);
return ans+sum;
}
