#include <bits/stdc++.h>
#include "aliens.h"
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxN = 510, maxK = 510;
const ll oo = 2e18;
ll las[maxN], dp[maxN], f[maxN];
int l[maxN], r[maxN];
vector <pii> que;
bool cmp(pii a1, pii a2)
{
if(a1.F != a2.F) return a1.F < a2.F;
return a1.S > a2.S;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
if(n > maxN) return -1;
for (int i=0; i<n; i++)
{
if(r[i] <= c[i])
c[i] ++;
else r[i] ++;
que.pb({min(r[i], c[i]), max(r[i], c[i])});
}
sort(que.begin(), que.end(), cmp);
int mx = -1, cnt = 0;
for (int i=0; i<n; i++)
{
if(mx >= que[i].S) continue ;
else
{
l[cnt] = que[i].F, r[cnt] = que[i].S;
mx = max(mx, que[i].S);
cnt ++;
}
}
n = cnt;
for (int i=0; i<=n; i++) las[i] = oo;
las[0] = 0;
for (int i=0; i<n-1; i++)
if(r[i] > l[i + 1]) f[i] = 1LL * (r[i] - l[i + 1]) * (r[i] - l[i + 1]);
for (int j=1; j<=k; j++)
{
dp[0] = 0;
for (int i=1; i<=n; i++)
{
dp[i] = oo;
for (int j=0; j<i; j++)
{
ll c;
if(j) c = f[j - 1];
else c = 0;
dp[i] = min(dp[i], (ll)(r[i - 1] - l[j]) * (r[i - 1] - l[j]) - c + las[j]);
}
}
for (int i=1; i<=n; i++)
las[i] = dp[i];
}
return dp[n];
}
