#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010;
const ll inf = 1ll << 55;
#include "aliens.h"
ll sq(ll v) { return v * v; }
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
for (int i = 0;i < n;++i) {
if (r[i] > c[i]) swap(r[i], c[i]);
}
vector<int> allc(c); allc.pb(-1); sort(AI(allc)), allc.erase(unique(AI(allc)), end(allc));
auto get_pos = [&](int c) -> int {
return lower_bound(AI(allc), c) - begin(allc);
};
int g = allc.size();
vector<vector<ll>> dp(g, vector<ll>(k + 1, inf)), osz(g, vector<ll>(k + 1, 0));
fill(AI(dp[0]), 0);
vector<vector<ll>> segmn(g, vector<ll>(g, inf));
vector<ll> omn(g, inf);
for (int i = 0;i < n;++i) {
int j = get_pos(c[i]);
chmin(omn[j], (ll)r[i]);
}
for (int i = 0;i < g;++i) {
segmn[i][i] = omn[i];
for (int j = i+1;j < g;++j)
segmn[i][j] = min(omn[j], segmn[i][j-1]);
}
// auto get_mn = [&](int ql, int qr) {
// return segmn[ get_pos(ql) ][ get_pos(qr) ];
//// ll ret = inf;
//// for (int i = 0;i < n;++i) {
//// if (ql <= c[i] && c[i] <= qr)
//// chmin(ret, (ll)r[i]);
//// }
//// assert(ret < inf);
//// return ret;
// };
debug(AI(allc));
for (int i = 1;i < g;++i) {
for (int j = 1;j <= k;++j) {
for (int l = 0;l < i;++l) {
//ll mnc = get_mn(allc[l]+1, allc[i]);
ll mnc = segmn[l+1][i];
ll wid = allc[i] - mnc + 1;
ll rep = max<ll>(0, allc[l] - mnc + 1);
if (rep > osz[l][j-1]) continue;
if (chmin(dp[i][j], dp[l][j-1] + sq(wid) - sq(rep)))
osz[i][j] = wid;
}
}
}
debug(AI(dp[g-1]));
return dp[g-1][k];
}
