#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000;
struct Segment {
int l, r;
} v[1+MAX_N];
struct cmp {
bool operator() (Segment a, Segment b) {
return a.l < b.l;
}
};
bool cmp2(Segment a, Segment b) {
return a.r < b.r || (a.r == b.r && a.l > b.l);
}
set<Segment, cmp> xd;
set<Segment, cmp>::iterator it;
void unify(int &n) {
std::sort(v, v + n, cmp2);
for(int i = 0; i < n; ++i) {
it = xd.lower_bound({v[i].l, 0});
while(it != xd.end())
it = xd.erase(it);
xd.insert(v[i]);
}
n = 0;
for(it = xd.begin(); it != xd.end(); it++)
v[++n] = *it;
}
struct Dreapta {
long long yinter, slope;
int photos;
};
deque<Dreapta> batch;
int top;
double intersect(Dreapta a, Dreapta b) {
return ((double)a.yinter - b.yinter) / (b.slope - a.yinter);
}
bool scoate(Dreapta a) {
if(top >= 2 && intersect(batch[top - 2], batch[top - 1]) >= intersect(batch[top - 2], a))
return true;
return false;
}
void addbatch(Dreapta x) {
while(top > 0 && scoate(x)) {
--top;
batch.pop_back();
}
++top;
batch.push_back(x);
}
long long querybatch(int x) {
while(top > 1 && x > intersect(batch[0], batch[1])) {
batch.pop_front();
--top;
}
return batch[0].yinter + batch[0].slope * x;
}
long long dp[1+MAX_N];
static inline long long sqr(long long x) {
return x * x;
}
bool check(int cost, int n, int k) {
batch.clear();
top = 0;
dp[0] = 0;
addbatch({(long long)sqr(v[1].l) - 2 * v[1].l,
-2 * v[1].l,
0});
for(int i = 1; i <= n; ++i) {
dp[i] = querybatch(v[i].r) + sqr(v[i].r + 1) + cost;
addbatch({(long long)sqr(v[i + 1].l) - 2 * v[i+1].l - sqr(max(0, (v[i].r - v[i+1].l + 1))) + dp[i],
-2 * v[i+1].l,
batch[0].photos + 1});
}
return batch[top - 1].photos <= k;
}
long long take_photos(int n, int m, int k, vector<int> _l, vector<int> _r) {
int a, b;
int st, dr;
for(int i = 0; i < n; ++i) {
a = _l[i];
b = _r[i];
v[i].l = min(a, b);
v[i].r = max(a, b);
}
unify(n);
st = 0;
dr = m * m + 1;
while(dr - st > 1) {
int mid = (st + dr) / 2;
if(check(mid, n, k))
dr = mid;
else
st = mid;
}
check(dr, n, k);
return dp[n] - batch[top - 1].photos * dr;
}
