#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sq(ll a) {return a * a;}
pair<ll, int> alien_solve(int m, const vector<pair<ll, ll>> &p, ll cost){
vector<pair<ll, int>> dp(p.size());
for (int i=0; i<dp.size(); i++){
dp[i] = make_pair(sq(p[i].second - p[0].first + 1) + cost, 1);
for (int j=1; j<=i; j++){
ll value = dp[j-1].first + sq(p[i].second - p[j].first + 1) -
sq(max(0LL, p[j-1].second - p[j].first + 1));
int used = dp[j-1].second + 1;
dp[i] = min(dp[i], make_pair(value + cost, used));
}
}
return dp.back();
}
vector<pair<ll, ll>> simplify(vector<pair<ll, ll>> &p){
sort(p.begin(), p.end(), [](const pair<ll, ll> &a, const pair<ll, ll> &b){
return make_pair(a.first, -a.second) < make_pair(b.first, -b.second);
});
vector<pair<ll, ll>> r; r.reserve(p.size());
for (const pair<ll, ll> &a: p){
if (r.size() && a.second <= r.back().second) continue;
r.push_back(a);
}
return r;
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
vector<pair<ll, ll>> p(n);
for (int i=0; i<n; i++) p[i] = minmax(r[i], c[i]);
p = simplify(p);
ll bl = 0, br = 1e12;
while (bl < br){
ll bm = (bl + br)>>1;
if (alien_solve(m, p, bm).second > k) bl = bm + 1;
else br = bm;
}
pair<ll, int> result = alien_solve(m, p, bl);
return result.first - result.second * bl;
}
