//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], prv[maxn];
struct line{
ll m, k;
line(){m = 0, k = inf;}
line(ll a, ll b){m = a, k = b;}
ll val(ll x){return m * x + k;}
};
void solve(){
deque<line> deq;
deq.push_back(line(-2 * l[1], l[1] * l[1]));
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] = min(prv[i], deq[0].val(r[i]) + r[i] * r[i]);
//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] + prv[i] - cj);
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 - lef.k, lef.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;
debug(l[i], r[i]);
prv[i] = inf;
}
prv[0] = 0;
for (int i = 0;i < k;i++) {
solve();
for (int j = 1;j <= siz;j++) prv[j] = dp[j];
}
return prv[siz];
}
