#include "aliens.h"
#include <iostream>
#include <algorithm>
#include <deque>
#define ll long long
#define ell __int128_t
#define pii pair<ll, ll>
#define fst first
#define snd second
#define ppi pair<pii, int>
const ll MN = -(ll)1e12 - 7, MX = 1;
using namespace std;
int N;
vector<pii> ivl;
deque<ppi> cht;
pii DP[100001];
ll Cs[100001];
inline bool validLine(const pii &l, const pii &m, const pii &r)
{
return (ell)(m.snd - l.snd) * (m.fst - r.fst) <= (ell)(r.snd - m.snd) * (l.fst - m.fst);
}
inline pii evalLine(const ppi &l, const int& x) {return {l.fst.fst * x + l.fst.snd, l.snd};}
inline pii solve(ll C)
{
cht.push_back({{-2 * ivl[0].fst, ivl[0].fst * ivl[0].fst}, 0});
for (int i = 0; i < N; i++)
{
while (cht.size() > 1 && evalLine(cht[0], ivl[i].snd) > evalLine(cht[1], ivl[i].snd)) {cht.pop_front();}
pii temp = evalLine(cht[0], ivl[i].snd);
DP[i] = {ivl[i].snd * ivl[i].snd + temp.fst - C, temp.snd + 1};
if (i + 1 < N)
{
ppi tempLine = {{-2 * ivl[i + 1].fst, DP[i].fst - Cs[i] + ivl[i + 1].fst * ivl[i + 1].fst}, DP[i].snd};
while (cht.size() > 1 && !validLine(cht[cht.size() - 2].fst, cht.back().fst, tempLine.fst)) {cht.pop_back();}
cht.push_back(tempLine);
}
//cerr << "DP: " << i << ", " << DP[i].fst << " " << DP[i].snd << "\n";
}
cht.clear();
return DP[N - 1];
}
inline void procIvl()
{
vector<pii> temp;
int L = ivl[0].fst, R = ivl[0].snd;
for (const auto &x : ivl)
{
if (x.snd > R)
{
if (L != x.fst) {temp.push_back({L - 1, R});}
L = x.fst, R = x.snd;
}
}
temp.push_back({L - 1, R});
//for (auto &x : temp) cerr << x.fst << " " << x.snd << "\n";
swap(ivl, temp);
N = ivl.size();
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
for (int i = 0; i < n; i++)
{
ivl.push_back({min(r[i], c[i]), max(r[i], c[i])});
}
sort(ivl.begin(), ivl.end());
procIvl();
k = min(k, N);
for (int i = 0; i + 1 < N; i++)
{
Cs[i] = max(0LL, ivl[i].snd - ivl[i + 1].fst);
Cs[i] *= Cs[i];
//cerr << "ISCT : " << i << ", " << Cs[i] << "\n";
}
ll L = MN, R = MX;
while (L < R)
{
ll M = L + R >> 1;
//cerr << "BSR: " << M << "\n";
pii res = solve(M);
if (res.snd <= k) L = M + 1;
else R = M;
}
pii res = solve(L - 1);
return res.fst + (L - 1) * k;
}
