#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct TConvexHullTrick {
struct TLine {
ll a;
ll b;
int id;
TLine(ll a = 0, ll b = 0, int id = 0)
: a(a), b(b), id(id) {
}
};
std::deque<TLine> Lines;
TConvexHullTrick() {
Lines.clear();
}
bool bad(const TLine& l1, const TLine& l2, const TLine& l3) {
return (l1.b - l3.b) * (l2.a - l1.a) < (l1.b - l2.b) * (l3.a - l1.a);
}
void add(ll a, ll b, int id) {
TLine line(a, b, id);
while (Lines.size() >= 2
&& bad(Lines[Lines.size() - 2], Lines[Lines.size() - 1], line)) {
Lines.pop_back();
}
Lines.push_back(line);
}
ll func(const TLine &d, ll x) {
return d.a * x + d.b;
}
std::pair<ll, int> get(ll x) {
while (Lines.size() >= 2 && func(Lines[0], x) > func(Lines[1], x)) {
Lines.pop_front();
}
return std::make_pair(func(Lines[0], x), Lines[0].id);
}
};
namespace Solver {
const int N = 1e5 + 5;
std::pair<int, int> input[N];
int l[N], r[N];
int n, m, k;
ll dp[N];
int trace[N];
void process() {
std::sort(input, input + n, [](const auto& x, const auto& y) {
return x.first < y.first || (x.first == y.first && x.second > y.second);
});
int rmax = -1;
int cnt = 0;
for (int i = 0; i != n; ++i) {
if (rmax < input[i].second) {
rmax = input[i].second;
++cnt;
l[cnt] = input[i].first;
r[cnt] = input[i].second;
}
}
n = cnt;
}
int check(ll lambda) {
TConvexHullTrick cht;
memset(dp, 0, sizeof dp);
memset(trace, 0, sizeof trace);
auto sqr = [](int i, int j, bool checkZero) {
if (!checkZero || r[j] >= l[i]) {
return (r[j] - l[i]) * 1ll *(r[j] - l[i]);
} else {
return 0ll;
}
};
cht.add(-2 * l[1], 1LL * l[1] * l[1], 0);
for (int i = 1; i <= n; ++i) {
pair<ll, int> g = cht.get(r[i]);
dp[i] = g.first + 1LL * r[i] * r[i] + lambda;
trace[i] = g.second;
ll bCoef = dp[i] - sqr(i + 1, i, true) + 1ll * l[i + 1] + l[i + 1];
cht.add(-2 * l[i + 1], bCoef, i);
}
int pos = n, cnt = 0;
while(pos) {
++cnt;
pos = trace[pos];
}
return cnt;
}
ll solve() {
process();
ll l = 0, r = 1e13;
while(l < r) {
ll mid = ((l + r) >> 1);
if (check(mid) <= k) {
r = mid;
} else {
l = mid + 1;
}
}
check(l); // l = lambda_opt
return dp[n] - l * k;
}
};
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
Solver::n = n;
Solver::m = m;
Solver::k = k;
for (int i = 0; i < n; ++i) {
if (r[i] > c[i]) {
std::swap(r[i], c[i]);
}
Solver::input[i].first = r[i];
Solver::input[i].second = ++c[i];
}
return Solver::solve();
}
