#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 solv1()
{
bool c[N][N] = {};
for (int i = 1; i <= n; ++i)
{
for (int x = a[i].l; x <= a[i].r; ++x)
{
for (int y = a[i].l; y <= a[i].r; ++y)
{
c[x][y] = true;
}
}
}
int ans = 0;
for (int x = 1; x <= m; ++x)
{
for (int y = 1; y <= m; ++y)
{
ans += c[x][y];
}
}
return ans;
}
int solv2()
{
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;
for (int u = i; u >= 1; --u)
{
dp[i][j] = min(dp[i][j], dp[u - 1][j - 1] + (a[i].r - a[u].r + 1) * (a[i].r - a[u].r + 1));
}
}
}
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;
}
if (n <= 50 && m <= 100 && k == n)
return solv1();
return solv2();
}
