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