#include <bits/stdc++.h>
#include "aliens.h"
#define dbg(x) cerr << (#x) << ": " << (x) << "; "
#define endline cerr << endl
using namespace std;
struct Line {
int photos;
long long a, b;
Line(long long a_ = 0LL, long long b_ = 0LL, int photos_ = 0) :
photos(photos_), a(a_), b(b_) {}
long long operator()(long long x) {
return a * x + b;
}
};
template<class T> long long Sqr(T x) {
return 1LL * x * x;
}
struct CHT {
int sz = 0;
deque<Line> dq;
bool IsUseless(Line old, Line nline, Line comp) {
if ((comp.b - nline.b) * (old.a - comp.a) == (nline.a - comp.a) * (comp.b - old.b))
return old.photos <= nline.photos;
return (comp.b - nline.b) * (old.a - comp.a) <= (nline.a - comp.a) * (comp.b - old.b);
}
void Insert(Line nline) {
while (sz >= 2 && IsUseless(dq[sz - 1], nline, dq[sz - 2])) {
dq.pop_back();
--sz;
}
dq.emplace_back(nline);
++sz;
}
long long Query(int x) {
while (sz >= 2 && (dq[0](x) > dq[1](x) ||
(dq[0](x) == dq[1](x) && dq[0].photos >= dq[1].photos))) {
dq.pop_front();
--sz;
}
return dq[0](x);
}
};
struct Solver { // 100 perhaps? ca cica asa se face
int n, m, k;
vector<pair<int, int>> points;
Solver(int n_, int m_, int k_, vector<int> &r, vector<int> &c) :
n(n_), m(m_), k(k_), points(n) {
for (int i = 0; i < n; ++i) {
if (r[i] > c[i])
swap(r[i], c[i]);
points[i] = {r[i], c[i]};
}
points = RemoveRedundant(points);
n = points.size() - 1;
}
long long Solve() {
auto Check = [&](long long cost) {
CHT cht;
cht.Insert(Line(-2 * points[1].first, Sqr(points[1].first), 0));
for (int i = 1; i <= n; ++i) {
int x = points[i].second + 1;
long long dp = cht.Query(x) + Sqr(x) + cost;
int photos = cht.dq.front().photos + 1;
if (i == n)
return make_pair(dp, photos);
Line nline(-2 * points[i + 1].first,
dp + Sqr(points[i + 1].first) -
Sqr(max(0, points[i].second - points[i + 1].first + 1)),
photos);
cht.Insert(nline);
}
};
long long lo = 0, hi = (long long)1e18, ans = (long long)1e18;
while (lo <= hi) {
long long mid = lo + (hi - lo) / 2LL;
auto ck = Check(mid);
if (ck.second <= k) {
ans = ck.first - k * mid;
hi = mid - 1;
} else
lo = mid + 1;
}
return ans;
}
long long Solve60() {
// points[i].first < points[i + 1].first
// points[i].second < points[i + 1].second
vector<CHT> cht(k + 1); // ar trebui sa mi pun semne de exclamare sa nu uit
for (int i = 0; i <= k; ++i)
cht[i].Insert(Line(-2 * points[1].first, Sqr(points[1].first)));
for (int i = 1; i <= n; ++i) {
for (int j = k; j >= 1; --j) {
int x = points[i].second + 1; // queries increasing
long long dp = cht[j - 1].Query(x) + Sqr(x);
if (i == n) {
return dp;
}
Line nline(-2 * points[i + 1].first, // slopes decreasing
dp + Sqr(points[i + 1].first) -
Sqr(max(0, points[i].second - points[i + 1].first + 1)));
cht[j].Insert(nline);
}
}
}
vector<vector<long long>> Brute() {
vector<vector<long long>> dp(n + 2, vector<long long>(k + 2, (long long)1e18));
fill(dp[0].begin(), dp[0].end(), 0LL);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
dp[i][j] = dp[i][k - 1];
for (int p = 0; p <= i - 1; ++p) {
dp[i][j] = min(dp[i][j],
dp[p][j - 1] + Sqr(points[i].second - points[p + 1].first + 1) -
Sqr(max(0, points[p].second - points[p + 1].first + 1))); // intersection
}
}
}
return dp;
}
vector<pair<int, int>> RemoveRedundant(vector<pair<int, int>> &v) {
sort(v.begin(), v.end(), [](const pair<int, int> &a, const pair<int, int> &b) {
if (a.first != b.first)
return a.first < b.first;
return a.second > b.second;
});
int max_rgt = -1;
vector<pair<int, int>> ret;
ret.emplace_back(-1, -1);
for (int i = 0; i < (int)points.size(); ++i) {
if (points[i].second > max_rgt) {
max_rgt = points[i].second;
ret.emplace_back(points[i]);
}
}
return ret;
}
};
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
Solver solver(n, m, k, r, c);
return solver.Solve();
}
