#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//ahmet23 orz...
//FatihSultanMehmedHan(ortanca da orz)
//AbdulhamidHan
//YavuzSultanSelimHan
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& is, pair<X,Y> &pr){return is>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr){return os<<pr.first<<" "<<pr.second;}
template<typename T> istream& operator>>(istream& is, vector<T> &arr){for (auto &it : arr) is>>it;return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T> arr){for (auto &it : arr) os<<it<<" ";return os;}
template<typename T, size_t Y> istream& operator>>(istream& is, array<T,Y> &arr){for (auto &it : arr) is>>it;return is;}
template<typename T, size_t Y> ostream& operator<<(ostream& os, array<T,Y> arr){for (auto &it : arr) os<<it<<" ";return os;}
template<typename T> void coutarr(T __arr){for (auto &it : __arr){cout<<it<<" ";}cout<<endl;}
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define endl '\n'
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define vint(x) vector<int> x
#define tol(bi) (1LL<<((int64_t)(bi)))
typedef long long ll;
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "aliens.h"
ll take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vector<bool> gerekli(n,true);
for (int i = 0; i < n; i++){
if (r[i]>c[i]) swap(r[i],c[i]);
for (int j = 0; j < i; j++){
if (r[i]>=r[j] && c[i]<=c[j]){
gerekli[i]=false;
}
else if (r[j]>=r[i] && c[j]<=c[i]){
gerekli[j]=false;
}
}
}
vector<pair<int,int>> arr;
for (int i = 0; i < n; ++i)
{
if (gerekli[i]) arr.push_back({r[i],c[i]});
}
n=arr.size();
sortarr(arr);
vector<vector<ll>> dp(n,vector<ll>(k+1,-1));
vector<vector<int>> opt(n,vector<int>(k+1,-1));
function<ll(int,int)> f;
f = [&](int node, int kal)->ll{
if (dp[node][kal]!=-1) return dp[node][kal];
dp[node][kal]=dp[node][kal]=((ll)arr.back().second-(ll)arr[node].first+1LL)*((ll)arr.back().second-(ll)arr[node].first+1LL);
opt[node][kal]=n-1;
if (node==n-1){
opt[node][kal]=node;
return dp[node][kal];
}
if (kal>1){
f(node,kal-1);
f(node+1,kal);
int i = node;
ll curdir = ((ll)arr[i].second-(ll)arr[node].first+1)*((ll)arr[i].second-(ll)arr[node].first+1);
ll azaldir = ((ll)arr[i].second-(ll)arr[i+1].first+1)*((ll)arr[i].second-(ll)arr[i+1].first+1);
if (((ll)arr[i].second-(ll)arr[i+1].first+1)<0){
azaldir=0;
}
ll crr = curdir-azaldir+f(i+1,kal-1);
if (crr<dp[node][kal]){
opt[node][kal]=i;
dp[node][kal]=crr;
}
for (int i = max(node,opt[node][kal-1]-1000); i <= min(opt[node+1][kal],n-2); i++){
ll curdir = ((ll)arr[i].second-(ll)arr[node].first+1)*((ll)arr[i].second-(ll)arr[node].first+1);
ll azaldir = ((ll)arr[i].second-(ll)arr[i+1].first+1)*((ll)arr[i].second-(ll)arr[i+1].first+1);
if (((ll)arr[i].second-(ll)arr[i+1].first+1)<0){
azaldir=0;
}
ll crr = curdir-azaldir+f(i+1,kal-1);
if (crr<dp[node][kal]){
opt[node][kal]=i;
dp[node][kal]=crr;
}
}
}
return dp[node][kal];
};
return f(0,k);
}
