#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 = 503;
struct ban
{
int l, r;
};
bool operator<(const ban& a, const ban& b)
{
return a.r < b.r;
}
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);
}
int solv3()
{
sort(a + 1, a + n + 1);
int dp[N][N] = {};
for (int i = 1; i <= n; ++i)
{
dp[i][0] = m * m;
for (int j = 1; j <= k; ++j)
{
dp[i][j] = m * m;
int minl = a[i].l;
for (int u = i; u >= 1; --u)
{
minl = min(minl, a[u].l);
if (u == 1)
{
dp[i][j] = min(dp[i][j], (a[i].r - minl + 1) * (a[i].r - minl + 1));
continue;
}
dp[i][j] = min(dp[i][j], dp[u - 1][j - 1] + (a[i].r - minl + 1) * (a[i].r - minl + 1)
- hat(m_p(minl, a[i].r), m_p(a[u - 1].l, a[u - 1].r)) * hat(m_p(minl, a[i].r), m_p(a[u - 1].l, a[u - 1].r)));
}
}
}
return dp[n][k];
}
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;
bool z[N] = {};
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
if (z[j])
continue;
if (i == j)
continue;
if (a[j].l <= a[i].l && a[i].r <= a[j].r)
{
z[i] = true;
break;
}
}
if (!z[i])
v.push_back(a[i]);
}
n = sz(v);
for (int i = 1; i <= n; ++i)
a[i] = v[i - 1];
k = min(k, n);
return solv3();
}
