#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
typedef long long LL;
typedef pair<LL, LL> PLL;
long long sq(long long z) {return z*z;}
PLL operator+(PLL a, PLL b) {
return PLL(a.first+b.first, a.second+b.second);
}
struct CHT {
vector<LL> M, C, P;
int ptr = 0;
///Use double comp if M,C is LL range
bool useless(int l1, int l2, int l3) {
return (C[l3]-C[l1])*(M[l1]-M[l2]) < (C[l2]-C[l1])*(M[l1]-M[l3]);
}
PLL f(int id, LL x) {
return {M[id]*x+C[id], P[id]+1};
}
void add(LL m, LL c, LL p) {
M.push_back(m);
C.push_back(c);
P.push_back(p);
int s = M.size();
while (s >= 3 && useless(s-3, s-2, s-1)) {
M.erase(M.end()-2);
C.erase(C.end()-2);
P.erase(P.end()-2);
s--;
}
}
PLL query(LL x) {
if (ptr >= M.size()) ptr = M.size()-1;
while (ptr < M.size()-1 && f(ptr, x) >= f(ptr+1, x)) ptr++; /// change > to < for maximum
return f(ptr, x);
}
};
int x[N], y[N];
PLL dp[N];
PLL check(long long c, int n, int *x, int *y) {
CHT cht;
for (int i=1; i<=n; i++) {
LL C = dp[i-1].first + sq(x[i]) - sq(max(0, y[i-1]-x[i]));
LL M = -2*x[i];
cht.add(M, C, dp[i-1].second);
dp[i] = cht.query(y[i]);
dp[i].first += sq(y[i]) + c;
}
return dp[n];
}
long long take_photos(int n, int N, int k, vector<int> xx, vector<int> yy) {
vector<pair<int, int>> ranges;
for (int i=0; i<n; i++) {
ranges.push_back({max(xx[i], yy[i]), -min(xx[i], yy[i])});
}
sort(ranges.begin(), ranges.end());
vector<pair<int, int>> r2;
for (auto pr: ranges) {
int r = pr.first, l = -pr.second;
while (r2.size() && r2.back().first >= l) r2.pop_back();
r2.push_back({l, r});
}
n = r2.size();
k = min(k, n);
for (int i=1; i<=n; i++) {
x[i] = r2[i-1].first, y[i] = r2[i-1].second+1;
}
long long lo = -1e12, hi = 1e12;
while (lo < hi) {
long long mid = lo + (hi-lo)/2;
if (check(mid, n, x, y).second > k) lo = mid+1;
else hi = mid;
}
return check(lo, n, x, y).first - k*lo;
}
