#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;
long double intersect(Dreapta a, Dreapta b) {
return ((double)a.yinter - b.yinter) / (b.slope - a.slope);
}
bool scoate(Dreapta a) {
if(top >= 2 && intersect(batch[top - 2], batch[top - 1]) >= intersect(batch[top - 2], a))
return true;
return false;
}
int pnt;
void addbatch(Dreapta x) {
while(top > 1 && scoate(x)) {
--top;
batch.pop_back();
}
++top;
if(pnt >= top)
pnt = top - 1;
batch.push_back(x);
}
long long querybatch(int x) {
while(pnt < top - 1 && x >= intersect(batch[pnt], batch[pnt + 1])) {
++pnt;
}
return batch[pnt].yinter + batch[pnt].slope * x;
}
long long dp[1+MAX_N];
static inline long long sqr(long long x) {
return x * x;
}
bool check(long long cost, int n, int k) {
batch.clear();
top = 0;
dp[0] = 0;
v[0].l = v[0].r = -1;
addbatch({dp[0] + sqr(v[1].l - 1) - 0,
-2 * v[1].l,
0});
for(int i = 1; i <= n; ++i) {
dp[i] = querybatch(v[i].r) + sqr(v[i].r + 1) - 1 + cost;
addbatch({ dp[i] + sqr(v[i + 1].l - 1) - sqr(max(0, v[i].r - v[i + 1].l + 1)),
-2 * v[i+1].l,
batch[pnt].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;
long long 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 = (long long)m * m + 1;
while(dr - st > 1) {
long long mid = (st + dr) / 2;
if(check(mid, n, k))
dr = mid;
else
st = mid;
}
check(st, n, k);
if(k > n)
k = n;
return dp[n] - st * k;
}
