/*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 1000000007ll
#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;
bool del(line a,line b,line c)
{
pair<LL, LL> x1, x2;
x1 = MP(c.b - a.b, a.k - c.k);
x2 = MP(c.b - b.b, b.k - c.k);
//assert(x1.second && x2.second);
if (b.k == c.k)
return c.b >= b.b;
if ((x1.second < 0) == (x2.second < 0))
return x1.first * x2.second > x2.first * x1.second;
else
return x1.first * x2.second < x2.first * x1.second;
}
LL getY(LL x,line p)
{
return x * p.k + p.b;
}
void build()
{
convex.clear();
}
void add(line p)
{
while (convex.size() >= 2 && del(convex[convex.size() - 2], convex[convex.size() - 1], p) )
convex.pop_back();
convex.PB(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;
vector<vector<LL>> dp;
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;
k = min(k, n);
dp.resize(k + 5, vector<LL>(n + 5, 0));
for (int i = 1; i <= n; i++)
dp[1][i] = (a[i].second - a[1].first + 1) * (a[i].second - a[1].first + 1);
for (int i = 2; i <= k; i++)
{
build();
for (int j = i - 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), 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)));
}
}
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 4 3
0 1
1 2
2 3
5 6 4
0 1
1 2
2 3
3 4
4 5
2 6 2
1 4
4 1
5 7 2
0 3
4 4
4 6
4 5
4 6
*/
