#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];
pair<long long,long long> d[100005];
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 double intersectie(pair<int,int> a, pair<int,int> b)
{
return 1.0 * (a.second - b.second) / (b.first - a.first);
}
long long solve_dp()
{
for(int i=1; i<=n; i++)
{
p[i] = v[i+1].first;
}
for(int j=1; j<=k; j++)
{
int st = 1, dr = 0;
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(j==1)
{
continue;
}
if(v[i-1].second < v[i].first)
{
dp[i][j] = 1LL * (v[i].second - v[i].first + 1) * (v[i].second - v[i].first + 1) + dp[i-1][j-1];
}
while(st<dr && intersectie(d[st],d[st+1]) < v[i].second)
{
++st;
}
if(st<=dr)
{
dp[i][j] = min(dp[i][j],1LL * v[i].second * v[i].second + d[st].first * v[i].second + d[st].second);
}
pair<int,int> new_val = {-2LL * (p[i] - 1),0};
if(p[i] > v[i].second)
{
new_val.second = dp[i][j-1] + 1LL * (p[i] - 1) * (p[i] - 1);
}
else
{
new_val.second = dp[i][j-1] - 1LL * v[i].second * v[i].second + 2LL * (p[i] - 1) * v[i].second;
}
while(st<dr && intersectie(new_val,d[dr]) < intersectie(d[dr],d[dr-1]))
{
--dr;
}
d[++dr] = new_val;
}
}
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
