#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = 9e18;
struct point {
long long x, y;
bool operator < (const point &p) const {
return x == p.x ? y < p.y : x < p.x;
}
};
struct line {
long long m, c, s;
line(long long m_, long long c_, long long s_) : m(m_), c(c_), s(s_), left(NULL), right(NULL) { };
long long eval(long long x) {
return m * x + c;
}
line *left, *right;
};
long long N, M;
vector<point> r;
vector<long long> dp;
vector<long long> cnt;
/*
struct lichaotree {
line* root;
lichaotree() : root(new line(0, INF, 0)) { };
line* insert(line* v, long long l, long long r, long long m_, long long c_, long long s_) {
if (v == NULL || l == r) return new line(m_, c_, s_);
long long m = l + r >> 1;
if (v->eval(m) > m_ * m + c_) swap(v->m, m_), swap(v->c, c_), swap(v->s, s_);
if (v->eval(l) > m_ * l + c_)
v->left = insert(v->left, l, m, m_, c_, s_);
else
v->right = insert(v->right, m + 1, r, m_, c_, s_);
return v;
}
pair<long long, long long> qry(line* &v, long long l, long long r, long long x) {
if (v == NULL) return {INF, 0};
if (l == r) return {v->eval(x), v->s};
long long m = l + r >> 1;
if (x <= m) return min(make_pair(v->eval(x), v->s), qry(v->left, l, m, x));
return min(make_pair(v->eval(x), v->s), qry(v->right, m + 1, r, x));
}
void insert(long long m, long long c, long long s) {
insert(root, 0, M, m, c, s);
}
pair<long long, long long> qry(long long x) {
return qry(root, 0, M, x);
}
};
*/
struct Line {
long long m = 0, c = 0;
int cnt = 0;
Line(long long _m, long long _c, int _cnt) : m(_m), c(_c), cnt(_cnt) { }
long long get(long long x) { return m * x + c; }
double intersection(Line o) { return (double) (o.c - c) / (double) (m - o.m); }
bool good(Line l2, Line l3) { return __int128(l2.c - c) * (l2.m - l3.m) < __int128(l3.c - l2.c) * (m - l2.m); }
};
struct CHT {
deque<Line> hull;
void insert(Line l) {
while (hull.size() > 1) {
auto last = hull.end()[-1];
auto p_last = hull.end()[-2];
if (p_last.good(last, l)) break;
hull.pop_back();
}
hull.push_back(l);
}
pair<long long, int> query(long long x) {
while (hull.size() > 1 && hull[0].get(x) > hull[1].get(x)) {
hull.pop_front();
}
return {hull[0].get(x), hull[0].cnt};
}
};
long long sq(long long x) {
return 1LL * x * x;
}
void aliens(long long lambda) {
CHT cht;
cht.insert(Line(-2 * r[0].x, sq(r[0].x) + 1 - 2 * r[0].x, 0));
for (long long i = 0; i < N; i++) {
auto [mn, cnt_] = cht.query(r[i].y);
dp[i] = mn + sq(r[i].y) + 2 * r[i].y + lambda;
cnt[i] = cnt_ + 1;
if (i < N - 1) {
cht.insert(Line(-2 * r[i + 1].x, dp[i] + sq(r[i + 1].x) - 2 * r[i + 1].x + 1 - sq(max(0LL, r[i].y - r[i + 1].x + 1)), cnt[i]));
}
}
}
long long take_photos(int n, int m, int K, vector<int> R, vector<int> C) {
vector<point> f;
r = vector<point> (), M = m;
long long k = K;
for (long long i = 0; i < n; i++) {
if (R[i] > C[i]) swap(R[i], C[i]);
f.push_back({R[i], C[i]});
}
sort(f.begin(), f.end());
r.push_back(f[0]);
for (long long i = 1; i < n; i++) {
if (r.back().x == f[i].x) {
r.pop_back();
r.push_back(f[i]);
} else if (f[i].y > r.back().y) {
r.push_back(f[i]);
}
}
N = r.size(), k = min(k, N);
dp = vector<long long> (N), cnt = vector<long long> (N);
long long l_ = 0, r_ = 1e17;
while (l_ <= r_) {
long long m_ = l_ + r_ >> 1;
aliens(m_);
if (l_ == r_) break;
if (cnt[N - 1] > k) l_ = m_ + 1;
else r_ = m_;
}
return dp[N - 1] - l_ * k;
}
