#include <bits/stdc++.h>
//#define home
#ifndef home
#include "aliens.h"
#endif // home
using namespace std;
const long long oo = LLONG_MAX;
int n,m,k;
long long R[100005],C[100005];
pair<long long,long long> v[100005],aux[100005];
long long p[100005];
long long dp[4005][4005];
void transform_input()
{
int new_n = 0;
for(int i=1; i<=n; i++)
{
int row = R[i];
int col = C[i];
if(row>=col)
{
C[i] = col;
R[i] = row;
}
else
{
C[i] = row;
R[i] = col;
}
aux[i].first = C[i];
aux[i].second = R[i];
}
auto cmp = [](pair<long long,long long> a, pair<long long,long long> b)
{
return (a.first < b.first || (a.first==b.first && a.second > b.second));
};
sort(aux+1,aux+n+1,cmp);
long long Max_r = 0;
for(int i=1; i<=n; i++)
{
if(Max_r < aux[i].second)
{
v[++new_n] = aux[i];
}
Max_r = max(Max_r,aux[i].second);
}
n = new_n;
}
long long solve_dp()
{
for(int i=1;i<=n;i++)
{
p[i] = v[i+1].first;
}
for(int j=1; j<=k; j++)
{
for(int i=1; i<=n; i++)
{
dp[i][j] = 1LL * (v[i].second - v[1].first + 1) * (v[i].second - v[1].first + 1);
if(v[i-1].second < v[i].first && j!=1)
{
dp[i][j] = 1LL * (v[i].second - v[i].first + 1) * (v[i].second - v[i].first + 1) + dp[i-1][j-1];
}
for(int c=1;c<i;c++)
{
if(p[c] > v[c].second)
{
continue;
}
dp[i][j] = min(dp[i][j], 1LL * v[i].second * v[i].second - 2LL * (p[c] - 1) * v[i].second + dp[c][j-1] - 1LL * v[c].second * v[c].second + 2LL * (p[c] - 1) * v[c].second);
}
}
}
return dp[n][k];
}
long long take_photos(int N, int M, int K, vector<int> r, vector<int> c)
{
n = N;
m = M;
k = K;
for(int i=0; i<n; i++)
{
R[i+1] = r[i] + 1;
C[i+1] = c[i] + 1;
}
transform_input();
return solve_dp();
}
#ifdef home
int main()
{
int nn,mm,kk;
vector<int> rr,cc;
cin>>nn>>mm>>kk;
rr.resize(nn);
cc.resize(nn);
for(int i=0; i<nn; i++)
{
cin>>rr[i]>>cc[i];
}
cout<<take_photos(nn,mm,kk,rr,cc)<<'\n';
return 0;
}
#endif
