#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <complex>
#include <chrono>
#include <random>
#include <stack>
#include <set>
#include <fstream>
#define FOR(i,n) for(int i = 0;i < n; i++)
#define FORE(i,a,b) for(int i = a; i <= b ; i++)
#define ss second
#define ff first
#define ll long long int
#define ii pair<ll,ll>
#define il pair<int,ll>
#define li pair<ll,int>
#define x ff
#define y ss
#define lii pair<ll,pair<int,int> >
#define piil pair<int ,pair<int,int> >
#define iii pair<pair<int,int>,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#include "aliens.h"
using namespace std;
const ll INF = 1e18;
vector<ii> all;
vector<ii> reduceList(vector<ii> v){
sort(v.begin(), v.end());
vector<ii> res;
for(auto e:v){
if(res.empty() or res.back().ff < e.ff)res.pb(e);
else{
res.back() = e;
}
}
return res;
}
vector<ii> createRanges(vi r,vi c,int n){
vector<ii> all;
FOR(i,n)all.pb({min(r[i],c[i]),max(r[i],c[i])});
return all;
}
ll cost(int t,int i){
i--;
//cout << "afsf " << i << " " << all.size() << endl;
ll t1 = all[i].ss - all[t].ff + 1; t1*=t1;
ll t2 = max((ll)0,(t-1 <0)?0:(all[t-1].ss-all[t].ff+1)); t2 *= t2;
//cout << t1 << " " << t2 << endl;
//cout << t1-t2 << endl;
return t1 - t2;
}
ll dp[4002][4002];
void computeDp(int k){
int n = all.size();
k = min(n,k);
//cout << n << " " << k << endl;
FOR(i,n)dp[0][i] = dp[i][0] = 0;
FOR(j,k+1){
if(j == 0)continue;
FORE(i,1,n){
ll opt = INF;
FORE(t,1,i){
opt = min(opt,dp[t-1][j-1] + cost(t-1,i));
}
dp[i][j] = opt;
}
}
}
ll take_photos(int n,int m,int k,vi r,vi c){
all = reduceList(createRanges(r,c,n));
//for(auto e:all)cout << e.ff<< ";"<<e.ss << endl;
computeDp(k);/*
FOR(i,min((int)all.size(),k)+1){
FOR(j,all.size()+1){
cout << dp[i][j] << " ";
};cout << endl;}*/
return dp[all.size()][min((int)all.size(),k)];
//return 0;
}
/*
int main(){
int a[5] = {0,4,4,4,4};
int b[5] = {3,4,6,5,6};
cout << take_photos(5,7,2,a,b) << endl;
return 0;
}
*/
