#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005;
const ll INF = 1000000009000000009;
struct ban
{
int l, r;
};
bool operator<(const ban& a, const ban& b)
{
if (a.r < b.r)
return true;
if (a.r > b.r)
return false;
return a.l > b.l;
}
int n, m, k;
ban a[N];
int hat(pair<int, int> a, pair<int, int> b)
{
return max(0, min(a.se, b.se) - max(a.fi, b.fi) + 1);
}
ll** dp;
void rec(int j, int l, int r, int ul, int ur)
{
if (l > r)
return;
int m = (l + r) / 2;
dp[m][j] = INF;
int mini;
for (int u = ur; u >= ul; --u)
{
ll yans;
if (u == 1)
yans = (a[m].r - a[u].l + 1) * 1LL * (a[m].r - a[u].l + 1);
else
yans = dp[u - 1][j - 1] + (a[m].r - a[u].l + 1) * 1LL * (a[m].r - a[u].l + 1)
- hat(m_p(a[u].l, a[m].r), m_p(a[u - 1].l, a[u - 1].r)) * 1LL * hat(m_p(a[u].l, a[m].r), m_p(a[u - 1].l, a[u - 1].r));
if (yans < dp[m][j])
{
dp[m][j] = yans;
mini = u;
}
}
rec(j, l, m - 1, ul, mini);
rec(j, m + 1, r, mini, ur);
}
ll solv3()
{
sort(a + 1, a + n + 1);
dp = new ll*[n + 5];
for (int i = 0; i < n + 5; ++i)
dp[i] = new ll[k + 5];
for (int i = 1; i <= n; ++i)
dp[i][0] = INF;
for (int j = 1; j <= k; ++j)
{
rec(j, 1, n, 1, n);
/*for (int j = 1; j <= k; ++j)
{
dp[i][j] = m * m;
for (int u = i; u >= 1; --u)
{
if (u == 1)
{
dp[i][j] = min(dp[i][j], (a[i].r - a[u].l + 1) * (a[i].r - a[u].l + 1));
continue;
}
dp[i][j] = min(dp[i][j], dp[u - 1][j - 1] + (a[i].r - a[u].l + 1) * (a[i].r - a[u].l + 1)
- hat(m_p(a[u].l, a[i].r), m_p(a[u - 1].l, a[u - 1].r)) * hat(m_p(a[u].l, a[i].r), m_p(a[u - 1].l, a[u - 1].r)));
}
}*/
}
return dp[n][k];
}
int t[N * 10 * 4];
void bil(int tl, int tr, int pos)
{
t[pos] = N * 10;
if (tl == tr)
{
return;
}
int m = (tl + tr) / 2;
bil(tl, m, pos * 2);
bil(m + 1, tr, pos * 2 + 1);
}
void ubd(int tl, int tr, int x, int y, int pos)
{
if (tl == tr)
{
t[pos] = min(t[pos], y);
return;
}
int m = (tl + tr) / 2;
if (x <= m)
ubd(tl, m, x, y, pos * 2);
else
ubd(m + 1, tr, x, y, pos * 2 + 1);
t[pos] = min(t[pos * 2], t[pos * 2 + 1]);
}
int qry(int tl, int tr, int l, int r, int pos)
{
if (l > r)
return N * 10;
if (tl == l && tr == r)
return t[pos];
int m = (tl + tr) / 2;
return min(qry(tl, m, l, min(m, r), pos * 2),
qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}
long long take_photos(int n_, int m_, int k_, std::vector<int> r, std::vector<int> c)
{
n = n_;
m = m_;
k = k_;
for (int i = 1; i <= n; ++i)
{
a[i].l = r[i - 1];
a[i].r = c[i - 1];
if (a[i].l > a[i].r)
swap(a[i].l, a[i].r);
++a[i].l;
++a[i].r;
}
vector<ban> v;
sort(a + 1, a + n + 1);
bil(1, m, 1);
for (int i = n; i >= 1; --i)
{
if (!(qry(1, m, a[i].r, m, 1) <= a[i].l))
v.push_back(a[i]);
ubd(1, m, a[i].r, a[i].l, 1);
}
n = sz(v);
for (int i = 1; i <= n; ++i)
a[i] = v[i - 1];
k = min(k, n);
return solv3();
}
