#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using real_t = long double;
template <typename T>
struct line {
T k, b;
[[nodiscard]] T apply(T x) const {
return k * x + b;
}
};
template <typename T>
real_t inter(line<T> const& a, line<T> const& b) {
return static_cast<real_t>(a.b - b.b) / (b.k - a.k);
}
template <typename T>
struct hull {
struct item {
line<T> l;
real_t from;
real_t to;
int cnt;
item(line<T> l_, real_t from_, real_t to_, int cnt_) : l(l_), from(from_)
, to(to_), cnt(cnt_) {}
};
vector<item> lines;
real_t const inf = 1e20;
int ptr = 0;
void add_line(line<T> const& l, int cnt) {
while ((int) lines.size() >= 2 &&
inter(l, lines.back().l) <=
inter(lines.back().l, lines[lines.size() - 2].l)) {
lines.pop_back();
}
if (lines.empty()) {
lines.emplace_back(l, -inf, inf, cnt);
} else {
auto x = inter(l, lines.back().l);
lines.back().to = x;
lines.emplace_back(l, x, inf, cnt);
}
}
pair<T, int> get(T x) {
ptr = min(ptr, (int) lines.size() - 1);
while (x > lines[ptr].to) {
++ptr;
}
return {lines[ptr].l.apply(x), lines[ptr].cnt};
}
};
i64 take_photos(int n, int, int mx, vector<int> r, vector<int> c) {
struct cell {
int r, c;
cell(int r_, int c_) : r(r_), c(c_) {}
};
vector<cell> a;
{
for (int i = 0; i < n; ++i) {
if (r[i] < c[i]) {
swap(r[i], c[i]);
}
}
vector<int> p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j) {
if (r[i] != r[j]) {
return r[i] < r[j];
}
return c[i] > c[j];
});
for (int i = 0; i < n; ++i) {
while (!a.empty() && a.back().c >= c[p[i]]) {
a.pop_back();
}
a.emplace_back(r[p[i]], c[p[i]]);
}
}
n = (int) a.size();
mx = min(mx, n);
auto calc = [&](i64 lam) -> pair<i64, int> {
auto sqr = [](i64 x) {
return x * x;
};
hull<i64> cht;
i64 cur = 0;
int cnt = 0;
for (int i = 0; i < n; ++i) {
auto ci = !i ? 0 : sqr(
max<i64>(0, a[i - 1].r - a[i].c + 1));
cht.add_line({-2 * a[i].c, sqr(a[i].c) + cur - ci},
cnt);
auto res = cht.get(a[i].r + 1);
cnt = res.second + 1;
cur = sqr(a[i].r + 1) + res.first + lam;
}
return {cur, cnt};
};
i64 left = 0;
i64 right = (i64) 1e13;
while (left + 1 != right) {
auto middle = (left + right) / 2;
auto[score, nsqs] = calc(middle);
if (nsqs > mx) {
left = middle;
} else {
right = middle;
}
}
auto get_cost = [](auto p, auto lam) {
return p.first - p.second * lam;
};
auto f_right = calc(right);
if (f_right.second == mx) {
return get_cost(f_right, right);
}
auto f_left = calc(left);
if (f_left.second == mx) {
return get_cost(f_left, left);
}
auto k = static_cast<long double>(get_cost(f_left, left) - get_cost(f_right,
right)) /
(f_left.second - f_right.second);
auto b = get_cost(f_left, left) - k * f_left.second;
return (i64) roundl(k * mx + b);
}
//i64 take_photos_ac(int n, int, int mx, vector<int> r, vector<int> c) {
// struct cell {
// int r, c;
//
// cell(int r_, int c_) : r(r_), c(c_) {}
// };
// vector<cell> a;
// {
// for (int i = 0; i < n; ++i) {
// if (r[i] < c[i]) {
// swap(r[i], c[i]);
// }
// }
// vector<int> p(n);
// iota(p.begin(), p.end(), 0);
// sort(p.begin(), p.end(), [&](int i, int j) {
// if (r[i] != r[j]) {
// return r[i] < r[j];
// }
// return c[i] > c[j];
// });
// for (int i = 0; i < n; ++i) {
// while (!a.empty() && a.back().c >= c[p[i]]) {
// a.pop_back();
// }
// a.emplace_back(r[p[i]], c[p[i]]);
// }
// }
// n = (int) a.size();
// mx = min(mx, n);
// i64 const INF = (i64) 1e18;
// vector<vector<i64>> dp(n + 1, vector<i64>(mx + 1, INF));
// fill(dp[0].begin(), dp[0].end(), 0);
// auto relax = [&](i64& x, i64 y) {
// if (y < x) {
// x = y;
// }
// };
// auto sqr = [](i64 x) {
// return x * x;
// };
// for (int k = 1; k <= mx; ++k) {
// hull<i64> cht;
// for (int i = 0; i < n; ++i) {
// // dp[i + 1][k]
// auto ci = !i ? 0 : sqr(
// max<i64>(0, a[i - 1].r - a[i].c + 1));
// cht.add_line({-2 * a[i].c, sqr(a[i].c) + dp[i][k - 1] - ci}, 0);
// dp[i + 1][k] = sqr(a[i].r + 1) + cht.get(a[i].r + 1).first;
// }
// }
// return dp.back().back();
//}
//#define STRESS
//
//int main() {
//#ifdef STRESS
// mt19937 rng(566);
// auto rnd = [&](auto from, auto to) {
// return uniform_int_distribution<decltype(from)>(from, to)(rng);
// };
// int const N = 30;
// int const M = 30;
// for (int it = 0; ; ++it) {
// cerr << it << '\n';
// if (it == 4) {
// cerr << "elegiggle\n";
// }
// int n = rnd(1, N);
// int m = rnd(1, M);
// vector<int> r(n);
// vector<int> c(n);
// for (int i = 0; i < n; ++i) {
// r[i] = rnd(0, m - 1);
// c[i] = r[i];
// }
// int k = rnd(1, n);
// auto ac = take_photos_ac(n, m, k, r, c);
// auto wa = take_photos(n, m, k, r, c);
// if (ac != wa) {
// cout << ac << ' ' << wa << endl;
// cout << n << ' ' << m << ' ' << k << endl;
// for (int i = 0; i < n; ++i) {
// cout << r[i] << ' ' << c[i] << endl;
// }
// return 0;
// }
// cout << "passed " << ac << endl;
// }
//#else
// vector<int> r{2, 3, 4, 5};
//// vector<int> r{1, 2, 3, 4};
// auto c = r;
// int m = 6;
// int k = 3;
// cout << take_photos((int) r.size(), m, k, r, c) << '\n';
//#endif
//}
//
///*
// 6 8
// 4 6 3
// 2 2
// 4 4
// 3 3
// 5 5
// */
