#include "aliens.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define befv(V) ((V)[sz(V)-2])
#define upmin(a,b) (a)=min((a),(b))
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;
ll pw(ll n) { return n*n; }
ll operator * (const pll &a, const pll &b) { return a.first*b.second - b.first*a.second; }
ll ccw(const pll &a, const pll &b, const pll &c) { return a*b + b*c + c*a; }
const int MAXN = 100055;
struct CHT {
pll P[MAXN];
int I[MAXN], n, pv;
void init() { n = pv = 0; }
void push(ll a, ll b, int c) {
pll p(a, b);
for(; 1 < n && 0 <= ccw(P[n-2], P[n-1], p); n--);
P[n] = p;
I[n] = c;
n++;
}
ll f(int i, ll X) { return P[i].first * X + P[i].second; }
pil get(ll X) {
if(n <= pv) pv = n-1;
for(ll nw, nxt; pv+1 < n; pv++) {
nw = f(pv, X); nxt = f(pv+1, X);
if(nw <= nxt) break;
}
return pil(I[pv], f(pv, X));
}
} cht;
ll C[MAXN], D[MAXN];
int E[MAXN];
int X[MAXN], Y[MAXN];
int N, M, K;
void push(int i) { cht.push(-2ll*X[i], D[i-1] + pw(X[i]) - C[i] - 2ll*X[i], i); }
int f(ll L) {
cht.init();
for(int i = 1; i <= N; i++) {
push(i);
pil ret = cht.get(Y[i]);
E[i] = E[ret.first-1] + 1;
D[i] = ret.second + pw(Y[i]+1) + L;
}
return E[N];
}
ll getAns() {
{
vector<pii> V, T;
for(int i = 1; i <= N; i++) {
if(X[i] > Y[i]) swap(X[i], Y[i]);
V.eb(X[i], Y[i]);
}
sorv(V);
for(auto &v : V) {
int x, y; tie(x, y) = v;
if(!T.empty() && T.back().first == x) T.back().second = y;
if(T.empty() || T.back().second < y) T.eb(x, y);
}
N = sz(T);
for(int i = 1; i <= N; i++) tie(X[i], Y[i]) = T[i-1];
}
if(N < K) K = N;
for(int i = 2; i <= N; i++)
C[i] = pw(max(0, Y[i-1] - X[i] + 1));
ll s = 0, e = pw(M)+5;
ll l = -1, ly, r = e+1, ry;
for(ll m; s <= e;) {
m = (s+e) >> 1;
int t = f(m);
ll y = D[N] - m * t;
if(t == K) return y;
if(K < t) {
s = m+1;
if(t < r) { r = t; ry = y; }
} else {
e = m-1;
if(l < t) { l = t; ly = y; }
}
}
return ry + (ly-ry) / (r-l) * (r-K);
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
::N = n;
::M = m;
::K = k;
for(int i = 1; i <= ::N; i++) {
::X[i] = r[i-1];
::Y[i] = c[i-1];
}
return getAns();
}
