#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;
vvi ps;
int sq(int x){
return x * x;
}
int sm(int x, int y){
return ps[y+1][y+1]-ps[x][y+1]-ps[y+1][x]+ps[x][x];
}
long long take_photos(signed n, signed m, signed k, std::vector<signed> r, std::vector<signed> c) {
vi p(m,-1); vector<vector<bool>>grid(m, vector<bool>(m)); 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; vpii v; f0r(i,m){
if(p[i] > mx){
mx=p[i]; v.pb(mp(i,p[i]));
}
} n = v.size(); //for(auto u : v)cout<<u.F<<' '<<u.S<<'\n';
ps.resize(m+1); f0r(i,m+1)ps[i].resize(m+1);
FOR(i,1,m+1)FOR(j,1,m+1)ps[i][j]=ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1]+grid[i-1][j-1];
int sum = ps[m][m]; vvi dp(n,vi(k+1,1e18)); f0r(i,n){
dp[i][1] = sq(v[i].S-v[0].F+1) - sm(v[0].F,v[i].S);
FOR(j,1,i+1){
int cost = sq(v[i].S-v[j].F+1) - sm(v[j].F,v[i].S);
FOR(l,2,k+1)dp[i][l] = min(dp[i][l], dp[j-1][l-1] + cost);
}
}
int ans = 4e18; f0r(i,k+1)ans = min(ans, dp[n-1][i]);
return ans+sum;
}
