#include <aliens.h>
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define filter(v) v.resize(unique(all(v)) - v.begin())
#define dbg(x) "[" #x " = " << (x) << "]"
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> bool maximize(T &a, T b) {
if(a < b) {
a = b;
return true;
}else return false;
}
template<typename T> bool minimize(T &a, T b) {
if(a > b) {
a = b;
return true;
}else return false;
}
template<typename T> T rnd(T a, T b) {
return uniform_int_distribution<T>(a, b)(rng);
}
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<long long, int> li;
const int N = 1e5 + 3;
int n, m, k;
int r[N], c[N];
pair<int, int> a[N];
li dp[N];
ll square(int x) {
return 1LL * x * x;
}
void better(li &x, li y) {
if(x.first == y.first) maximize(x, y);
else minimize(x, y);
}
li f(ll lambda) {
dp[1] = li(square(a[1].second - a[1].first) + lambda, 1);
for(int i = 2; i <= n; i++) {
dp[i] = li(LLONG_MAX, 0);
for(int j = 1; j < i; j++) {
better(dp[i], ii(
dp[j].first + square(a[i].second - a[i].first) - square(a[j].second - a[i].first) + lambda,
dp[j].second + 1
));
}
}
return dp[n];
}
ll process() {
vector<ii> segments;
for(int i = 1; i <= n; i++) {
segments.emplace_back(min(r[i], c[i]), max(r[i], c[i]));
}
sort(all(segments), [&](ii a, ii b){
return (a.first == b.first ? a.second > b.second : a.first < b.first);
});
vector<ii> tmp;
for(auto [l, r] : segments) {
if(tmp.empty() || tmp.back().second < r)
tmp.emplace_back(l, r);
}
n = sz(tmp);
for(int i = 1; i <= n; i++) {
a[i] = tmp[i - 1];
a[i].first--;
}
ll l = 1, r = 1LL * m * m, result = 0;
while(l <= r) {
ll mid = (l + r) >> 1;
if(f(mid).second >= k) result = mid, l = mid + 1;
else r = mid - 1;
}
return f(result).first - k * result;
return 0;
}
ll take_photos(int _n, int _m, int _k, int _r[], int _c[]) {
n = _n;
m = _m;
k = _k;
for(int i = 1; i <= n; i++) {
r[i] = _r[i - 1] + 1;
c[i] = _c[i - 1] + 1;
}
return process();
}
