#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
void debug_out() {cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 1e5 + 10;
int n, m, k;
pll dp[maxn];
ll x[maxn], y[maxn], z[maxn];
vector<pll> p;
struct CHT{
static const ll inf = 1e18;
int l, r;
vector<pll> a;
CHT(int _n){
a.resize(_n);
l = r = 0;
}
ll insec(int l1, int l2){
assert(x[l1] != x[l2]);
if (x[l1] > x[l2]) swap(l1, l2);
return (y[l1] - y[l2] + (y[l1] <= y[l2]? 0: 1) * (x[l2] - x[l1] - 1)) / (x[l2] - x[l1]);
}
void add(int idx){
ll tmp;
while(r){
tmp = insec(a[r-1].S, idx);
//debug(tmp);
if (x[a[r-1].S] * tmp + y[a[r-1].S] == x[idx] * tmp + y[idx] && z[a[r-1].S] < z[idx]) tmp++;
if (tmp <= a[r-1].F) r--;
else break;
}
if (!r) a[r++] = {-inf, idx};
else a[r] = {tmp, idx}, r++;
//debug(r-1, a[r-1].F, a[r-1].S);
}
pll get(ll tmp){
while(l + 1 < r && a[l+1].F <= tmp) l++;
return MP(x[a[l].S] * tmp + y[a[l].S], z[a[l].S]);
}
};
pll Calc(ll lan){
//debug(lan);
CHT cht(n);
dp[0] = {(p[0].S - p[0].F) * (p[0].S - p[0].F) + lan, 1};
x[0] = -p[0].F;
y[0] = p[0].F * p[0].F;
z[0] = 0;
//debug(x[0], y[0], z[0]);
//debug(dp[0].F, dp[0].S);
cht.add(0);
for (int i = 1; i < n; i++){
/*dp[i] = {(p[i].S-p[0].F) * (p[i].S-p[0].F) + lan, 1};
for (int j = 1; j <= i; j++){
dp[i] = min(dp[i], MP(dp[j-1].F + (p[i].S-p[j].F)*(p[i].S-p[j].F) - (p[j-1].S > p[j].F? (p[j-1].S-p[j].F) * (p[j-1].S-p[j].F): 0) + lan, dp[j-1].S + 1));
}*/
x[i] = -p[i].F;
y[i] = dp[i-1].F + p[i].F * p[i].F - (p[i-1].S > p[i].F? (p[i-1].S-p[i].F)*(p[i-1].S-p[i].F): 0);
z[i] = dp[i-1].S;
//debug(x[i], y[i], z[i]);
cht.add(i);
pll val = cht.get(2*p[i].S);
dp[i] = {val.F + (p[i].S) * (p[i].S) + lan, val.S+1};
//debug(i, dp[i].F, dp[i].S);
}
return dp[n-1];
}
const int maxa = 1e6 + 10;
int mx[maxa];
long long take_photos(int _n, int _m, int _k, std::vector<int> R, std::vector<int> C) {
/*CHT cht(n);
x[0] = ;
y[0] = 2;
x[1] = 10;
y[1] = 15;
return cht.insec(0, 1);*/
memset(mx, -1, sizeof mx);
n = _n, m = _m, k = _k;
for (int i = 0; i < n; i++){
if (R[i] > C[i]) swap(R[i], C[i]);
mx[R[i]] = max(mx[R[i]], C[i]);
}
for (int i = 0; i < m; i++){
if (mx[i] == -1) continue;
if (p.empty() || (p.back().S) < mx[i]) p.push_back({i, mx[i]});
}
k = min(k, (int)p.size());
n = p.size();
for (int i = 0; i < n; i++){
//debug(i, p[i].F, p[i].S);
p[i].S++;
}
ll l = -1, r = 1e12;
while(l + 1 < r){
//debug(l, r);
ll mid = (l + r) >> 1;
pll tmp = Calc(mid);
if (tmp.S <= k) r = mid;
else l = mid;
}
//debug(r);
pll tmp = Calc(r);
return tmp.F - r * k;
}
