#include <bits/stdc++.h>
#include "aliens.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MX=1009;
const ll inf = (1ll<<60);
ll dp[MX][MX];
vector<pii>v1;
bool cmp(pii a,pii b){
if(a.second == b.second)
return a.first > b.first;
return a.second < b.second;
}
int n,k;
vector<pair<ll,ll> >a;
ll take_photos(int N, int m, int K, vector<int> r, vector<int> c) {
n=N;k=K;
for(int i=0;i<n;i++){
if(r[i] > c[i])swap(c[i],r[i]);
v1.push_back({c[i],r[i]});
}
sort(v1.begin(),v1.end(),cmp);
a.push_back({-5,-5});
a.push_back(v1[0]);
for(int i=1;i<n;i++){
if(v1[i].first <= a.back().first) continue;
a.push_back(v1[i]);
}
n=a.size() - 1;
sort(a.begin(),a.end());
// for(auto pp:a)cout<<pp.first<<" "<<pp.second<<endl;
for(int i=1;i<=n;i++)dp[0][i]=inf;
dp[0][0]=0;
for(int u=1;u<=k;u++){
for(int i=1;i<=n;i++)dp[u][i]=inf;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
ll Cost = (a[i].first - a[j].second + 1) * (a[i].first - a[j].second + 1);
ll Inter = (max(0ll,a[j-1].first - a[j].second + 1)) * (max(0ll,a[j-1].first - a[j].second + 1));
dp[u][i] = min(dp[u][i], dp[u-1][j-1] + Cost - Inter);
}
}
}
return dp[k][n];
}
/*
5 7 2
0 3
4 4
4 6
4 5
4 6
*/
