#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 4005;
const long long inf = 1e18;
long long dp[maxn][maxn];
long long cost[maxn][maxn];
void divide(int k, int l, int r, int optl, int optr)
{
if (l > r)
{
return;
}
int mid = (l + r) / 2;
int best = optl;
for (int i = optl; i <= min(optr, mid); ++i)
{
if (dp[k][mid] > dp[k - 1][i - 1] + cost[i][mid])
{
dp[k][mid] = dp[k - 1][i - 1] + cost[i][mid];
best = i;
}
}
divide(k, l, mid, optl, best);
divide(k, mid + 1, r, best, optr);
}
long long calc(long long x)
{
return x * x;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
vector<pair<long long, long long>> v;
for (int i = 0; i < n; ++i)
{
if (r[i] > c[i])
{
swap(r[i], c[i]);
}
v.push_back(make_pair(r[i], -c[i]));
}
sort(v.begin(), v.end());
vector<pair<long long, long long>> v2;
v2.push_back(make_pair(-1, -1));
long long max_num = -1;
for (int i = 0; i < n; ++i)
{
if (-v[i].second > max_num)
{
max_num = -v[i].second;
v2.push_back(make_pair(v[i].first, -v[i].second));
}
}
n = v2.size() - 1;
k = min(k, n);
for (int i = 0; i <= k; ++i)
{
for (int j = 0; j <= n; ++j)
{
dp[i][j] = inf;
}
}
for (int j = 0; j <= k; ++j)
{
dp[j][0] = 0LL;
}
for (int i = 1; i <= n; ++i)
{
long long curr_max = 0;
for (int j = i; j <= n; ++j)
{
curr_max = max(curr_max, v2[j].second);
cost[i][j] = calc(curr_max - v2[i].first + 1) - (i > 1 ? calc(max(0LL, v2[i - 1].second - v2[i].first + 1)) : 0);
}
}
for (int j = 1; j <= n; ++j)
{
dp[1][j] = cost[1][j];
}
for (int i = 2; i <= k; ++i)
{
divide(i, 1, n, 1, n);
}
return dp[k][n];
}
