#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl
#define REP(i, n) for (Long i = 0; i < (Long)n; i++)
using namespace std;
typedef long long Long;
//https://contest.yandex.com/ioi/contest/2830/problems/F/
const Long INF = 1e18;
struct Line {
Long m, b, cnt;
//mx + b, intersect with next line at r (rounded down)
Line() {}
Line(Long m, Long b, Long cnt): m(m), b(b), cnt(cnt) {}
Long getVal(Long x) {return m * x + b;}
};
struct CHT{
deque<Line> envelope;
Long div(Long a, Long b) { //floored division
//CAREFUL ! this won't produced the right convex envelope
//but the maxY function will still work for integers
//if you need the correct convex envelope, use double division
//or multiplication in "bad" function
assert(b != 0);
return a / b - ((a ^ b) < 0 && a % b);
}
Long intersect(Line l1, Line l2) {
return div(l1.b - l2.b, l2.m - l1.m);
}
bool bad(Line l1, Line l2, Line l3) {
//tells if l2 is bad an can be eliminated by l3
return intersect(l2 , l3) <= intersect(l1, l2);
}
void addLine(Line l3) {
l3.m *= -1;
l3.b *= -1;
if (envelope.empty()) {
envelope.push_back(l3);
return;
}
if (l3.m == envelope.back().m) {
if (l3.b > envelope.back().b) envelope.pop_back();
else return;
}
if (envelope.size() <= 1) {
envelope.push_back(l3);
return;
}
Long sz = envelope.size();
Line l1 = envelope[sz - 2];
Line l2 = envelope[sz - 1];
while (bad(l1, l2, l3)) {
envelope.pop_back();
if (envelope.size() == 1) break;
sz = envelope.size();
l1 = envelope[sz - 2];
l2 = envelope[sz - 1];
}
envelope.push_back(l3);
}
pair<Long, Long> minY(Long x) { //O(log n)
assert(!envelope.empty());
while (envelope.size() >= 2 && envelope[0].getVal(x) < envelope[1].getVal(x)) {
envelope.pop_front();
}
return {-envelope[0].getVal(x), envelope[0].cnt};
}
};
struct Range {
int l, r;
Range(int l, int r): l(l), r(r){}
bool operator <(const Range &other) {
return r < other.r;
}
bool contains(Range &other) {
return l <= other.l && other.r <= r;
}
};
void removeContained(vector<Range> &v) {
int n = v.size();
vector<Range> ans = {v.back()};
for (int i = n - 2; i >= 0; i--) {
if (ans.back().contains(v[i])) continue;
ans.push_back(v[i]);
}
reverse(ans.begin(), ans.end());
v = ans;
}
Long square(Long x) {
return x * x;
}
vector<int> L, R;
Long cost(int l, int r) {
Long ans = square(R[r] - L[l]);
if (l > 0) ans -= square(max(0, R[l - 1] - L[l]));
return ans;
}
pair<Long, Long> getBest(Long lambda, int k) {
//returns <P(lambda, x), g(x)>
int n = L.size();
CHT cht;
vector<Long> dp(n);
vector<Long> cnt(n);
auto getLine = [&](int i) {
return Line(-2 * L[i + 1],
dp[i] + square(L[i + 1]) - square(max(0, R[i] - L[i + 1])), cnt[i]);
};
cht.addLine(Line(-2 * L[0], + square(L[0]), 0));
for (int i = 0; i < n; i++) {
tie(dp[i], cnt[i]) = cht.minY(R[i]);
dp[i] += square(R[i]) - lambda;
cnt[i]++;
if (i + 1 < n) cht.addLine(getLine(i));
}
return {dp[n - 1] + lambda * k, cnt[n - 1] - k};
}
bool check(Long lambda, int k) {
return getBest(lambda, k).second <= 0;
}
const Long INF2 = 1e13;
Long minCost(int k) { //O(logn)
// T T T ... F F F
Long low = -INF2;
Long high = INF2;
if (check(high, k)) return getBest(high, k).first; //all T
while (high - low > 1) {
Long mid = low + (high - low) / 2;
if (check(mid, k)) low = mid;
else high = mid;
}
//2 values low -> T and high-> F
return getBest(low, k).first;
}
Long take_photos(int n, int m, int K, vector<int> x, vector<int> y) {
vector<Range> v;
REP(i, n) {
int l = min(x[i], y[i]);
int r = max(x[i], y[i]);
v.push_back({l, r});
}
sort(v.begin(), v.end());
removeContained(v);
n = v.size();
L = R = vector<int>(n);
REP(i, n) {
v[i].r++;
L[i] = v[i].l;
R[i] = v[i].r;
}
K = min(K, n);
return minCost(K);
}
/*
5 8 5
1 5
3 4
2 6
1 4
3 5
ans = 34
7 30 5
1 5
3 4
2 6
1 4
3 5
9 15
14 22
ans = 160
*/
/*int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<int> x(n);
vector<int> y(n);
REP(i, n) {
cin >> x[i] >> y[i];
}
cout << take_photos(n, m, k, x, y) << "\n";
return 0;
}*/
