#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using ll = long long;
using pii = pair<int,int> ;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const int INF =(1<<30)-1;
const ll INFL = (1ll<<61)-1;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vector<pll> v(n);
for(int i = 0; i < n; i++){
v[i] = {r[i],c[i]};
if(r[i]-c[i] > 0){
v[i].ff = m-v[i].ff-1;
v[i].ss = m-v[i].ss-1;
}
}
vector<pll> pareto{{-1,-1}};
sort(all(v),[&](pll a, pll b){
if(a.ff == b.ff)
return a.ss > b.ss;
return a.ff < b.ff;
});
for(int i = 0; i < n; i++){
if(pareto.back().ss < v[i].ss)
pareto.push_back(v[i]);
}
n = pareto.size();
swap(v,pareto);
matrix<ll> dp(k+1,vector<ll>(n,INFL));
for(int i = 0; i <= k; i++)
dp[i][0] = 0;
// cout << "----\n";
// for(pll i : v)
// cout << i.ff << ' ' << i.ss << '\n';
for(int i = 1; i <= k; i++){
for(int j = 1; j < n; j++){
for(int l = 1; l <= j; l++){
ll newarea = (v[j].ss-v[l].ff+1)*(v[j].ss-v[l].ff+1);
if(v[l].ff <= v[l-1].ss){
newarea-=(v[l-1].ss-v[l].ff+1)*(v[l-1].ss-v[l].ff+1);
}
dp[i][j] = min(dp[i][j],dp[i-1][l-1]+newarea);
//cout << i << ' ' << j << ' ' << l << ' ' << newarea << '\n';
}
}
}
return dp[k][n-1];
}
