// M
#include<bits/stdc++.h>
#include "aliens.h"
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
struct CHT
{
typedef pair < ld , ld > Line;
deque < pair < ld , pair < Line , int > > > A;
ld INF = 1e18;
inline void Add(Line X, int i)
{
while (A.size() && Intersection(A.back().second.first, X) <= A.back().first)
A.pop_back();
if (A.size())
A.push_back({Intersection(A.back().second.first, X), {X, i}});
else
A.push_back({-INF, {X, i}});
}
inline int GetMax(ld X)
{
while (A.size() > 1 && A[1].first <= X)
A.pop_front();
return A[0].second.second;
}
inline ld Intersection(Line X, Line Y)
{
if (X.first == Y.first)
return X.second <= Y.second ? -INF : INF;
return (X.second - Y.second) / (Y.first - X.first);
}
};
const int N = 100005;
int n, m, k, Cnt[N];
ll CutOff[N];
ld dp[N];
pair < int , int > A[N];
inline int Solve(ld md)
{
CHT C;
auto Add = [&](int i){
C.Add(make_pair(2LL * (A[i + 1].y - 1), - dp[i] + CutOff[i] - (ll)(A[i + 1].y - 1) * (A[i + 1].y - 1)), i);
};
auto GetValue = [&](int i, int j){
return (dp[j] - CutOff[j] + (ll)(A[i].x - A[j + 1].y + 1) * (A[i].x - A[j + 1].y + 1));
};
Add(0);
for (int i = 1; i <= n; i ++)
{
int j = C.GetMax(A[i].x);
Cnt[i] = Cnt[j] + 1;
dp[i] = GetValue(i, j) + md;
Add(i);
}
return Cnt[n];
}
long long take_photos(int _n, int _m, int _k, vector < int > _R, vector < int > _C)
{
n = _n; m = _m; k = _k;
for (int i = 0; i < n; i ++)
A[i] = {_C[i], _R[i]};
for (int i = 0; i < n; i ++)
if (A[i].x < A[i].y)
swap(A[i].x, A[i].y);
vector < int > MN(m, m);
for (int i = 0; i < n; i ++)
MN[A[i].x] = min(MN[A[i].x], A[i].y);
n = 0;
for (int i = m - 1; i >= 0; i --)
if (MN[i] != m)
if (!n || A[n].y > MN[i])
A[++ n] = make_pair(i, MN[i]);
reverse(A + 1, A + n + 1);
k = min(k, n);
for (int i = 1; i < n; i ++)
if (A[i].x >= A[i + 1].y)
CutOff[i] = (ll)(A[i].x - A[i + 1].y + 1) * (A[i].x - A[i + 1].y + 1);
// Phew ..
ld le = 0, ri = 1e13, md;
for (int __ = 0; __ <= 60; __ ++)
{
md = (le + ri) * 0.5;
if (Solve(md) >= k)
le = md;
else
ri = md;
}
Solve(le);
return (ll)(dp[n] - k * le + 0.5);
}
