#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/
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;
}
struct OptRange {
int l, r, opt;
OptRange(int l, int r, int opt): l(l), r(r), opt(opt){}
};
Long getBest(Long lambda, int k) {
int n = L.size();
vector<Long> dp(n);
dp[0] = cost(0, 0) - lambda;
deque<pair<int, int>> ranges = {{1, -1}};
auto getOptimum = [&](int i, int opt) {
if (opt == -1) return cost(0, i) - lambda;
assert(opt + 1 <= i);
return dp[opt] + cost(opt + 1, i) - lambda;
};
for (int i = 0; i + 1 < n; i++) {
assert(ranges.front().first == i + 1);
auto improve = [&](int pos, int opt) {
return getOptimum(pos, i) < getOptimum(pos, opt);
};
int high = n - 1;
while (!ranges.empty() && improve(ranges.back().first, ranges.back().second)) {
high = ranges.back().first - 1;
ranges.pop_back();
}
if (ranges.empty()) ranges.push_back({i + 1, i});
else {
int low = ranges.back().first;
int opt = ranges.back().second;
if (!improve(high, opt)) low = high++;
// F F F ... T T T
while (high - low > 1) {
int mid = (low + high) / 2;
if (improve(mid, opt)) high = mid;
else low = mid;
}
if (high < n) ranges.push_back({high, i});
}
dp[i + 1] = getOptimum(i + 1, ranges.front().second);
ranges.front().first++;
if (ranges.size() > 1 && ranges[0].first >= ranges[1].first) ranges.pop_front();
}
return dp[n - 1] + lambda * k;
}
const Long INF2 = 1e13;
Long minCost(int k) { //O(log n)
Long low = -INF2;
Long high = INF2;
while (high - low > 2) {
Long m1 = low + (high - low) / 3;
Long m2 = high - (high - low) / 3;
if (getBest(m1, k) < getBest(m2, k)) low = m1;
else high = m2;
}
Long maxi = getBest(low, k);
for (Long i = low + 1; i <= high; i++) {
maxi = max(maxi, getBest(i, k));
}
return maxi;
}
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;
}*/
