#include<bits/stdc++.h>
using namespace std;
#define all(x) begin(x),end(x)
#define sz(x) int(x.size())
using ll = long long;
using ld = long double;
struct Line {
ll m, b, k;
mutable ld p; //we need to change p in the set
Line(ll _m, ll _b, ll _k) : m(_m), b(_b), k(_k), p(0) {}
bool operator<(const Line& o) const { //order by slope
return m < o.m;
}
bool operator<(ld x) const {
return p < x;
}
ld intersectX(const Line l) const {
return ld(b - l.b) / (l.m - m);
}
};
struct LineContainer : multiset<Line, less<>> {
static constexpr ld INF = 1e18;
bool intersect(iterator x, iterator y) {
if (y == end()) {
x->p = INF;
return false;
}
if (x->m == y->m) { //parallel
if (x->b > y->b) x->p = INF;
else x->p = -INF;
} else {
x->p = x->intersectX(*y);
}
return x->p >= y->p;
}
void add(ll m, ll b, ll k) {
auto next = emplace(m, b, k);
auto prev = next, curr = next;
next++;
while (intersect(curr, next)) {
next = erase(next);
}
if (prev != begin() && intersect(--prev, curr)) {
curr = erase(curr);
intersect(prev, curr);
}
curr = prev;
while (curr != begin() && (--prev)->p >= curr->p) {
curr = erase(curr);
intersect(prev, curr);
curr = prev;
}
}
pair<ll, ll> query(ll x) {
assert(!empty());
Line l = *lower_bound(x);
return {l.m * x + l.b, l.k};
}
};
struct Point {
ll x, y;
Point(ll _x, ll _y) : x(_x), y(_y) {}
};
ll take_photos(int n, int /*m*/, int k, vector<int> r, vector<int> c){
vector<Point> v;
for (int i = 0; i < n; i++) {
if (r[i] < c[i]) swap(r[i], c[i]);
v.emplace_back(r[i], c[i]);
}
sort(all(v), [](const Point &a, const Point &b) {
if (a.y != b.y) return a.y < b.y;
return a.x > b.x;
});
vector<Point> p{v[0]};
for (int i = 1; i < n; i++) {
if (p.back().x < v[i].x) p.push_back(v[i]);
}
n = sz(p);
k = min(k, n);
auto sq = [](ll x) { return x * x; };
auto check = [&](ll lambda) {
LineContainer dp;
ll res = 0, cnt = 0;
for (int i = 0; i < n; i++) {
ll m = -2LL * (p[i].y - 1LL);
ll b = res + sq(p[i].y - 1LL);
if (i > 0) b -= sq(max(p[i - 1].x - p[i].y + 1LL, 0LL));
dp.add(m, b, cnt);
tie(res, cnt) = dp.query(p[i].x);
res += sq(p[i].x) + lambda, cnt++;
}
return pair<ll, ll>{res, cnt};
};
ll lo = 0, hi = 1e13;
while (hi - lo > 1) {
ll mid = (hi - lo) / 2 + lo;
if (check(mid).second <= k) hi = mid;
else lo = mid;
}
return check(hi).first - k * hi;
}
