//#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
struct point {
int x, y;
bool operator < (const point &p) const {
return x == p.x ? y < p.y : x < p.x;
}
};
struct line {
int m;
long long c;
int s;
line(int m_, long long c_, int s_) : m(m_), c(c_), s(s_), left(NULL), right(NULL) { };
long long eval(int x) {
return 1LL * m * x + c;
}
line *left, *right;
};
int N, M;
vector<point> r;
struct lichaotree {
line* root;
lichaotree() : root(NULL) { };
void insert(line* &v, int l, int r, int m_, long long c_, int s_) {
if (v == NULL || l == r) {
v = new line(m_, c_, s_);
return;
}
int m = l + r >> 1;
if (make_pair(v->eval(m), v->s) > make_pair(1LL * m_ * m + c_, s_)) swap(v->m, m_), swap(v->c, c_), swap(v->s, s_);
if (make_pair(v->eval(l), v->s) > make_pair(1LL * m_ * l + c_, s_)) insert(v->left, l, m, m_, c_, s_);
else insert(v->right, m + 1, r, m_, c_, s_);
}
pair<long long, int> qry(line* &v, int l, int r, int x) {
if (v == NULL) return {INF, 0};
if (l == r) return {v->eval(x), v->s};
int m = l + r >> 1;
if (x <= m) return min({v->eval(x), v->s}, qry(v->left, l, m, x));
return min({v->eval(x), v->s}, qry(v->right, m + 1, r, x));
}
void insert(int m, long long c, int s) {
insert(root, 0, M, m, c, s);
}
pair<long long, int> qry(int x) {
return qry(root, 0, M, x);
}
};
long long sq(int x) {
return 1LL * x * x;
}
pair<long long, int> aliens(long long lambda) {
lichaotree lct;
lct.insert(-2 * r[0].x, sq(r[0].x) + 1 - 2 * r[0].x, 0);
for (int i = 0; i < N; i++) {
auto mn = lct.qry(r[i].y);
long long dp = mn.first + sq(r[i].y) + 2 * r[i].y + lambda;
if (i == N - 1) return {dp, -mn.second + 1};
lct.insert(-2 * r[i + 1].x, dp + sq(r[i + 1].x) - 2 * r[i + 1].x + 1 - sq(max(0, r[i].y - r[i + 1].x + 1)), mn.second - 1);
}
}
long long take_photos(int n, int m, int k, vector<int> R, vector<int> C) {
vector<point> f;
r = vector<point> (), M = m;
for (int 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 (int 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(N - 1, k);
long long l_ = 0, r_ = 1e15;
while (l_ < r_) {
long long m_ = l_ + r_ >> 1;
if (aliens(m_).second > k) l_ = m_ + 1;
else r_ = m_;
}
auto [dp, cnt] = aliens(l_);
return dp - l_ * cnt;
}
