//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<60;
int siz = 0;
ll l[maxn], r[maxn];
ll dp[maxn], num[maxn];
struct line{
ll m, k, cnt;
line(){m = 0, k = inf, cnt = 0;}
line(ll a, ll b, ll c){m = a, k = b, cnt = c;}
ll val(ll x){return m * x + k;}
};
void solve(ll cost){
deque<line> deq;
deq.push_back(line(-2 * l[1], l[1] * l[1] + cost, 0));
for (int i = 1;i <= siz;i++) {
while (deq.size() > 1 && deq[0].val(r[i]) >= deq[1].val(r[i])) deq.pop_front();
dp[i] = deq[0].val(r[i]) + r[i] * r[i];
num[i] = deq[0].cnt + 1;
//add line
if (i == siz) continue;
ll cj = max(0LL, r[i] - l[i+1]);
cj *= cj;
line add(-2*l[i+1], l[i+1] * l[i+1] + dp[i] - cj + cost, num[i]);
auto cdiv = [&] (ll p, ll q){ //ceil
if (q < 0) p = -p, q = -q;
if (p < 0) return p / q;
else return (p + q - 1) / q;
};
while (deq.size() > 1) {
line lef = deq[deq.size()-2], rig = deq.back();
if (cdiv(add.k - rig.k, rig.m - add.m) <= cdiv(rig.k - lef.k, lef.m - rig.m)) {
deq.pop_back();
} else {
break;
}
}
deq.push_back(add);
}
}
long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> C) {
vector<pii> seg;
for (int i = 0;i < n;i++) {
seg.push_back({min(R[i], C[i]), max(R[i], C[i]) + 1});
}
sort(seg.begin(), seg.end(), [&] (pii x, pii y){return x.ss == y.ss ? x.ff > y.ff : x.ss < y.ss;});
vector<pii> stk;
for (int i = 0;i < n;i++) {
while (stk.size() && seg[i].ff <= stk.back().ff) stk.pop_back();
stk.push_back(seg[i]);
}
siz = stk.size();
for (int i = 1;i <= siz;i++) {
l[i] = stk[i-1].ff, r[i] = stk[i-1].ss;
}
ll low = 0, up = 1LL<<40;
while (low < up - 1) {
ll mid = (low + up) / 2;
for (int i = 1;i <= siz;i++) dp[i] = inf, num[i] = 0;
num[0] = 0, dp[0] = 0;
solve(mid);
if (num[siz] >= k) {
low = mid;
} else {
up = mid;
}
}
for (int i = 1;i <= siz;i++) dp[i] = inf, num[i] = 0;
num[0] = 0, dp[0] = 0;
solve(low);
return -low * k + dp[siz];
}
