#include "aliens.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
struct dpstruct
{
int n;
int k;
vector<int> l;
vector<int> r;
int cost(int a, int b)
{
b--;
int bs = r[b] - l[a] + 1;
int ovlp = 0;
if (a > 0) ovlp = max(r[a - 1] - l[a] + 1, 0ll);
int ret = (bs*bs) - (ovlp*ovlp);
// cerr << a << " " << b << " " << bs << " " << ovlp << " " << ret << "\n";
return ret;
}
int calc()
{
k = min(k, n);
vector<int> dp(n + 1, 1e17);
vector<int> olddp(n + 1, 1e17);
dp[0] = 0;
olddp[0] = 0;
for (int i = 0; i < k; i++)
{
swap(dp, olddp);
int curr = 0;
for (int j = 1; j <= n; j++)
{
while (curr < j - 1)
{
if (olddp[curr] + cost(curr, j) >= olddp[curr + 1] + cost(curr + 1, j)) curr++;
else break;
}
dp[j] = olddp[curr] + cost(curr, j);
}
/*
for (int j : dp) cerr << j << " ";
cerr << "\n";
*/
}
return dp[n];
}
};
int take_photos(signed n, signed m, signed k, vector<signed> r, vector<signed> c)
{
vector<pair<int,int>> prs;
for (int i = 0; i < n; i++)
{
prs.emplace_back(min(r[i], c[i]), -max(r[i], c[i]));
}
sort(prs.begin(), prs.end());
vector<int> nl;
vector<int> nr;
nl.push_back(prs[0].first);
nr.push_back(-prs[0].second);
int last = -prs[0].second;
for (int i = 1; i < n; i++)
{
prs[i].second = -prs[i].second;
if (last < prs[i].second)
{
nl.push_back(prs[i].first);
nr.push_back(prs[i].second);
}
last = max(prs[i].second, last);
}
dpstruct dps;
dps.n = nl.size();
dps.k = k;
dps.l = nl;
dps.r = nr;
return dps.calc();
}
