#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template <class T>
void read(T &x)
{
x = 0;
register int c;
while ((c = getchar()) && (c > '9' || c < '0'))
;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
}
constexpr bool typetest = 0;
constexpr int N = 1e5 + 5;
constexpr ll Inf = 1e17;
int m, n, k;
pair<int, int> a[N];
ll cnt[N], sum[N];
struct ConvexHullTrick
{
vector<ll> A, B;
vector<int> line;
vector<ld> point;
ConvexHullTrick()
{
point.emplace_back(-Inf);
}
ld ff(int x, int y)
{
return (ld)1.0 * (B[y] - B[x]) / (A[x] - A[y]);
}
void Add(int i)
{
while ((int)line.size() > 2 || ((int)line.size() == 1 && A[line.back()] == A[i]))
{
if (A[line.back()] == A[i])
{
if (B[line.back()] > B[i])
{
line.pop_back();
if (!line.empty())
point.pop_back();
}
else
break;
}
else
{
if (ff(i, line.back()) <= ff(i, line[line.size() - 2]))
{
line.pop_back();
if (!line.empty())
point.pop_back();
}
else
break;
}
}
if (line.empty() || A[line.back()] != A[i])
{
if (!line.empty())
point.emplace_back(ff(line.back(), i));
line.emplace_back(i);
}
}
ll More(int x)
{
return cnt[x - 1] * a[x].second + sum[x - 1];
}
ll Get(int x)
{
int j = lower_bound(point.begin(), point.end(), a[x].second) - point.begin();
return A[line[j - 1]] * a[x].second + B[line[j - 1]] + More(x);
}
} f[4002];
long long take_photos(int N, int M, int K, vector<int> r, vector<int> c)
{
/* Convert */
m = M;
n = N;
k = K;
for (int i = 1; i <= n; ++i)
{
a[i] = make_pair(r[i - 1] + 1, c[i - 1] + 1);
if (a[i].first > a[i].second)
swap(a[i].first, a[i].second);
}
sort(a + 1, a + n + 1, [&](const pair<int, int> &x, const pair<int, int> &y)
{ return x.second < y.second || (x.second == y.second && x.first > y.first); });
vector<int> s;
for (int i = 1; i <= n; ++i)
{
while (!s.empty() && a[i].first <= a[s.back()].first)
s.pop_back();
s.emplace_back(i);
}
n = s.size();
for (int i = 1; i <= n; ++i)
a[i] = a[s[i - 1]];
/* End Convert */
long long temp(0);
for (int i = 1, j = 1, now = 0; i <= m; ++i)
{
if (j <= n && a[j].first == i)
{
now = a[j].second;
++j;
}
if (now >= i)
temp += 2 * (now - i + 1) - 1;
}
for (int i = 1; i <= n; ++i)
{
if (i == n)
{
cnt[i] = (a[i].second - a[i].first + 1) * 2;
sum[i] = -cnt[i] * a[i].second;
}
else if (a[i].second < a[i + 1].first)
{
cnt[i] = (a[i].second - a[i].first + 1) * 2;
sum[i] = -cnt[i] * a[i].second;
sum[i] += -1ll * (a[i + 1].first - a[i].second - 1) * (a[i + 1].first + a[i].second) + (a[i + 1].first - a[i].second - 1);
cnt[i] += 2 * (a[i + 1].first - a[i].second - 1);
}
else
{
cnt[i] = (a[i + 1].first - a[i].first) * 2;
sum[i] = -cnt[i] * a[i].second;
}
cnt[i] += cnt[i - 1];
sum[i] += sum[i - 1];
}
ll ans(Inf);
for (int i = 0; i <= k && i <= n; ++i)
{
f[i].A.resize(n + 2, 0);
f[i].B.resize(n + 2, 0);
}
f[0].A[0] = 0;
f[0].B[0] = 0;
f[0].Add(0);
for (int i = 1; i <= n; ++i)
for (int j = min(i, k); j; --j)
{
ll v = f[j - 1].Get(i);
f[j].A[i] = -cnt[i];
f[j].B[i] = -sum[i] + v;
f[j].Add(i);
if (i == n)
ans = min(ans, v);
}
return ans + temp;
}
void Read()
{
int m, n, k;
cin >> n >> m >> k;
vector<int> x(n), y(n);
for (int i = 0; i < n; ++i)
cin >> x[i] >> y[i];
cout << take_photos(n, m, k, x, y);
}
void Solve()
{
}
/*
*/
