#include <bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
using ll = long long;
using ld = long double;
struct Line {
ll m, b, k;
ll operator()(ll x) {
return m * x + b;
}
ll intersect(Line o) {
return ceil((ld)(o.b - b) / (m - o.m));
}
};
struct LineContainer : deque<pair<Line, ll>> {
void add(ll m, ll b, ll k) {
Line A = Line{m, b, k};
while (!empty()) {
auto [B, p] = back();
if (A(p) <= B(p)) pop_back();
else break;
}
ll p = 0;
if (!empty()) {
p = A.intersect(back().first);
}
emplace_back(A, p);
}
pair<ll,int> query(ll x) {
while (size() > 1 && at(1).first(x) <= at(0).first(x)) {
pop_back();
}
auto [l, p] = at(0);
return {l(x), l.k};
}
};
struct Point {
ll x, 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.push_back({R[i], C[i]});
}
sort(all(v), [](Point a, Point b) {
if (a.x != b.x) return a.x < b.x;
return a.y > b.y;
});
vector<Point> p{{-1, -1}};
for (int i = 0; i < n; i++) {
if (v[i].y > p.back().y) 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 = 1; i < n; i++) {
ll m = -2LL * (p[i].x - 1);
ll b = res + sq(p[i].x - 1) - sq(max(p[i - 1].y - p[i].x + 1, 0LL));
dp.add(m, b, cnt);
tie(res, cnt) = dp.query(p[i].y);
res += sq(p[i].y) + lambda;
cnt++;
}
return pair<ll, ll>{res, cnt};
};
ll lo = 0, hi = 1e13;
ll ans = 0;
while (hi - lo > 1) {
ll mid = (lo + hi) / 2;
auto [res, cnt] = check(mid);
if (cnt <= k) hi = mid, ans = res - cnt * mid;
else lo = mid;
}
return ans;
}
