#include<bits/stdc++.h>
using namespace std;
const long long MAXN = 1e5+7;
const long long INF = 1e18;
pair<long long, long long> tt[MAXN];
vector<pair<long long, long long> > a;
long long dp[MAXN][2], n, m, k;
bool cmp(pair<long long, long long> a1, pair<long long, long long> b1)
{
if(a1.first < b1.first) return true;
if(a1.first > b1.first) return false;
if(a1.second > b1.second) return true;
return false;
}
void f(long long l, long long r, long long ol, long long orr, long long kk)
{
if(l > r) return;
long long mid = (l+r)/2;
long long mini = INF, minii = -1;
for(long long i = ol; i <= min(orr, mid); i++)
{
long long curr = (a[mid].second-a[i].first+1)*(a[mid].second-a[i].first+1);
if(i-1 >= 0) curr += dp[i-1][(kk-1)%2]-max(0LL, a[i-1].second-a[i].first+1)*max(0LL, a[i-1].second-a[i].first+1);
if(curr < mini)
{
mini = curr;
minii = i;
}
}
dp[mid][kk%2] = mini;
f(l, mid-1, ol, minii, kk);
f(mid+1, r, minii, orr, kk);
return;
}
long long take_photos(int nn, int mm, int ks, vector<int> r, vector<int> c)
{
n = nn;
m = mm;
k = ks;
for(long long i = 1; i <= n; i++)
{
tt[i].first = min(c[i-1], r[i-1]);
tt[i].second = max(c[i-1], r[i-1]);
}
sort(tt+1, tt+n+1, cmp);
long long maxi = -1;
for(long long i = 1; i <= n; i++)
{
if(tt[i].second > maxi)
{
maxi = tt[i].second;
a.push_back(tt[i]);
}
}
for(long long i = 0; i < a.size(); i++)
{
dp[i][1] = (a[i].second-a[0].first+1)*(a[i].second-a[0].first+1);
}
for(long long i = 2; i <= k; i++)
{
f(0, a.size()-1, 0, a.size()-1, i);
}
int idx = a.size()-1;
return dp[idx][k%2];
}
