#include "aliens.h"
#include <bits/stdc++.h>
#define NO_DEBUG
using namespace std;
using lint = long long;
const lint INF = 1e15;
struct Segment {
lint left, right;
Segment(lint l = 0, lint r = 0): left(l), right(r) {}
bool operator < (const Segment &o) const {
return left < o.left || (left == o.left && right > o.right);
}
bool operator == (const Segment &o) const {
return left == o.left && right == o.right;
}
};
int N, K;
vector<Segment> segment;
vector<vector<lint>> memo;
lint cost(int i, int n) {
lint weight, offset;
weight = segment[n].right - segment[i].left + 1;
offset = max(0ll, segment[i - 1].right - segment[i].left + 1);
return (weight * weight) - (offset * offset);
}
lint dp(int n, int k) {
if (k < 0)
return INF;
if (n == 0)
return 0;
if (memo[n][k] != -1)
return memo[n][k];
lint &res = memo[n][k] = INF;
for (int i = 1; i <= n; i++)
res = min(res, dp(i - 1, k - 1) + cost(i, n));
return res;
}
void preprocess() {
sort(segment.begin(), segment.end());
vector<Segment> tmp;
tmp.emplace_back(-1, -1);
for (auto s : segment) {
Segment overlap = Segment(min(tmp.back().left, s.left), max(tmp.back().right, s.right));
if (overlap == s) swap(s, tmp.back());
if (overlap == tmp.back()) continue;
tmp.emplace_back(s);
}
return void((segment = tmp, N = segment.size() - 1, memo.assign(N + 1, vector<lint>(K + 1, -1))));
}
lint take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
N = n, K = k;
for (int i = 0; i < N; i++)
segment.emplace_back(min(r[i], c[i]), max(r[i], c[i]));
preprocess();
#ifndef NO_DEBUG
cerr << "SEGMENTS:\n";
for (int i = 1; i <= N; i++) cerr << segment[i].left << " " << segment[i].right << "\n";
#endif
return dp(N, K);
}
