/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <ctype.h>
#include <fstream>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
struct line
{
LL k, b;
line(LL K = 0, LL B = 0)
{
k = K;
b = B;
}
};
vector<line> convex;
double getY(line p, line q)
{
double k1, k2, b1, b2, x;
b1 = p.b;
k1 = p.k;
b2 = q.b;
k2 = q.k;
x = (b2 - b1) / (k1 - k2);
return k1 * x + b1;
}
LL getY(LL x,line p)
{
return x * p.k + p.b;
}
void build()
{
convex.resize(0);
}
void add(line p)
{
while (convex.size() >= 2 && getY(convex[convex.size() - 2], p) >= getY(convex[convex.size() - 1], p))
convex.pop_back();
convex.push_back(p);
}
bool check(int pos,LL x)
{
if (pos + 1 != convex.size() && getY(x, convex[pos + 1]) < getY(x, convex[pos]))
return 0;
if (pos - 1 >= 0 && getY(x, convex[pos]) < getY(x, convex[pos - 1]))
return 0;
return 1;
}
LL get(LL x)
{
int l, r, m;
LL ans = -mod * mod;
l = 0;
r = convex.size() - 1;
while (l <= r)
{
m = (l + r) / 2;
ans = max(ans, getY(x, convex[m]));
if (check(m, x))
l = m + 1;
else
r = m - 1;
}
return ans;
}
int n, m, k;
vector<pair<int, int>> c;
vector<pair<LL, LL>> a,p;
LL dp[102][50005];
int Main()
{
for (int i = 0; i < c.size(); i++)
{
if (c[i].first > c[i].second)
swap(c[i].first, c[i].second);
p.PB(MP(c[i].first, c[i].second));
}
sort(all(p), [](pair<LL, LL> a, pair<LL, LL> b) {
if (a.first != b.first)
return a.first < b.first;
return b.first > a.first;
});
a.PB(MP(-1, -1));
for (int i = 0; i < p.size(); i++)
if (a.back().second < p[i].second)
a.PB(p[i]);
n = a.size() - 1;
for (int i = 1; i <= n; i++)
dp[1][i] = (a[i].second - a[1].first + 1) * (a[i].second - a[1].first + 1);
k = min(k, n);
for (int i = 2; i <= k; i++)
{
build();
for (int j = 1; j <= i - 1; j++)
add(line(2 * (a[j + 1].first - 1),max(a[j].second-a[j+1].first+1,0ll)* max(a[j].second - a[j + 1].first + 1,0ll) -dp[i-1][j] - (a[j + 1].first - 1)* (a[j + 1].first - 1)));
for (int j = i; j <= n; j++)
{
dp[i][j] = -get(a[j].second) + a[j].second* a[j].second;
if(j!=n)
add(line(2 * (a[j + 1].first - 1), (a[j].second - a[j + 1].first + 1) * (a[j].second - a[j + 1].first + 1) - dp[i - 1][j] - (a[j + 1].first - 1) * (a[j + 1].first - 1)));
}
}
return 0;
}
LL take_photos(int N, int M, int K, vector<int> y, vector<int> x)
{
n = N;
m = M;
k = K;
while (!y.empty())
{
c.PB(MP(y.back(),x.back()));
y.pop_back();
x.pop_back();
}
Main();
return dp[k][n];
}
#ifdef death
int main()
{
int N, M, K;
vector<int> R, C;
cin >> N >> M >> K;
for (int i = 0; i < N; i++)
{
R.PB(0);
C.PB(0);
cin >> R.back() >> C.back();
}
cout << take_photos(N, M, K, R, C) << endl;
return 0;
}
#endif
/*
3 6 2
0 1
1 4
3 5
2 6 2
1 4
4 1
5 7 2
0 3
4 4
4 6
4 5
4 6
*/
