#include <bits/stdc++.h>
#define double long double
#include "aliens.h"
using namespace std;
const int N_MAX = 100002;
const double E = 0.000001;
typedef long long ll;
double sq(double x)
{
return x * x;
}
int n, m, k;
struct Point
{
int x, y;
};
bool operator < (const Point &a, const Point &b)
{
return make_pair(a.y, -a.x) > make_pair(b.y, -b.x);
}
Point v[N_MAX];
ll X[N_MAX], Y[N_MAX];
struct Line
{
double a, b;
int index;
double eval (double x)
{
return a * x + b;
}
};
bool ftest (const Line &l1, const Line &l2, const Line &l3)
{
return (l2.b - l1.b) * (l2.a - l3.a) < (l3.b - l2.b) * (l1.a - l2.a);
}
deque <Line> dq;
void update (Line l)
{
while(dq.size() >= 2 && ftest(dq.end()[-2], dq.end()[-1], l) == false)
dq.pop_back();
dq.push_back(l);
}
void query (double x, double &answer, int &index)
{
while(dq.size() >= 2 && dq[0].eval(x) >= dq[1].eval(x))
dq.pop_front();
answer = dq.front().eval(x);
index = dq.front().index;
}
double dp[N_MAX];
int steps[N_MAX];
void push (int i)
{
double a = -2 * X[i + 1];
double b = dp[i] + sq(X[i + 1]) - 2 * X[i + 1] - sq(max(0LL, Y[i] - X[i + 1] + 1));
update(Line{a, b, i});
}
void compute (double C)
{
while(!dq.empty())
dq.pop_back();
Y[0] = X[1] - 1;
push(0);
for(int i = 1; i <= n; i++)
{
double q;
int index;
query(Y[i], q, index);
dp[i] = sq(Y[i]) + 2 * Y[i] + 1 + C + q;
steps[i] = steps[index] + 1;
if(i == n)
break;
push(i);
}
}
ll take_photos(int _n, int _m, int _k, vector <int> _r, vector <int> _c)
{
n = _n;
m = _m;
k = _k;
for(int i = 1; i <= n; i++)
{
v[i].x = _r[i - 1];
v[i].y = _c[i - 1];
if(v[i].x > v[i].y)
swap(v[i].x, v[i].y);
}
sort(v + 1, v + n + 1);
int posy = 1;
Y[1] = v[1].y;
X[1] = v[1].x;
for(int i = 1; i <= n; i++)
if(i > 1 && v[i].y < v[i - 1].y && v[i].x < X[posy])
{
posy++;
Y[posy] = v[i].y;
X[posy] = v[i].x;
}
n = posy;
reverse(X + 1, X + n + 1);
reverse(Y + 1, Y + n + 1);
double l = 0, r = 1000000000000;
int cnt = 64;
while(cnt--)
{
double mid = (l + r) / 2;
compute(mid);
if(steps[n] > k)
l = mid + E;
else
r = mid;
}
compute(l);
return (ll) round(dp[n] - l * k);
}
