#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define SQ(x) ((long long)(x)*(x))
using ii = pair<long long,int>;
using point = array<int,2>;
struct Line {
int m; long long c; int u;
ii eval(int x) { return ii((long long)m*x + c, u); }
};
struct ConvexHull {
deque<Line> dq;
long double intersect(Line p, Line q) { return (long double)(p.c-q.c)/(q.m-p.m); }
void add(int m, long long c, int u) {
Line l = {m,c,u};
while (SZ(dq) > 1 && intersect(dq[SZ(dq)-1],dq[SZ(dq)-2]) <= intersect(dq[SZ(dq)-1],l))
dq.pop_back();
dq.push_back(l);
}
ii query(int x) {
while (SZ(dq) > 1 && dq[0].eval(x) >= dq[1].eval(x)) dq.pop_front();
return dq[0].eval(x);
}
};
ii monge(int n, vector<point> p, long long lcost) {
ii dp = ii(0,0);
ConvexHull ch;
RFOR(i,n-1,0){
// dp[i] = dp[j] + SQ(p[j][1] - p[i][0] + 1) + SQ(max(0,p[j][1] - p[j+1][0] + 1));
long long overlap = SQ(max(0,p[i][1] - p[i+1][0] + 1));
ch.add(-2*(p[i][1]+1), dp.first + SQ(p[i][1]+1) - overlap, dp.second);
dp = ch.query(p[i][0]);
dp.first += SQ(p[i][0]) + lcost;
dp.second += 1;
//cout << "dp " << i << " :: " << dp.first << " " << dp.second << endl;
}
return dp;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vector<point> p, q;
FOR(i,0,n-1){
if (r[i] > c[i]) swap(r[i],c[i]);
p.push_back(point({r[i],c[i]}));
}
sort(p.begin(),p.end(),[](point a, point b) {
if (a[0] == b[0]) return a[1] > b[1];
return a[0] < b[0]; });
for (auto& x : p) {
if (!q.empty() && x[1] <= q.back()[1]) continue;
q.push_back(x);
}
n = SZ(q), k = min(k,n);
q.push_back(point({m,m}));
long long lo = 0, hi = (long long)m*m+1;
while (hi-lo > 1) {
long long mid = (lo+hi)/2;
auto res = monge(n,q,mid);
if (res.second <= k) hi = mid;
else lo = mid;
}
auto ans = monge(n,q,hi);
return ans.first - k*hi;
}
