#include <bits/stdc++.h>
using namespace std;
const long long oo = 1LL << 60;
struct Line
{
long long a, b;
int id;
long long calc(long long x)
{
return a * x + b;
}
};
struct Hull
{
deque<Line> q;
int isBad(Line x, Line y, Line z)
{
return (x.b - z.b) * (z.a - y.a) >= (y.b - z.b) * (z.a - x.a);
}
void add(long long a, long long b, int id)
{
Line l = {a, b, id};
while (size(q) >= 2 && isBad(q[size(q) - 2], q.back(), l))
q.pop_back();
q.push_back(l);
}
pair<long long, int> query(long long x)
{
while (size(q) >= 2 && q[0].calc(x) > q[1].calc(x))
q.pop_front();
return {q[0].calc(x), q[0].id};
}
};
long long sqr(long long x)
{
return x * x;
}
pair<long long, int> solve(vector<pair<int, int>> &a, long long penalty)
{
int n = size(a) - 1;
Hull hull;
vector<pair<long long, int>> f(n + 1, pair<int, int>(oo, 0)); // (cost, number of photos)
f[0] = {0, 0};
for (int i = 1; i <= n; i++)
{
long long curB = f[i - 1].first + sqr(a[i].first) - sqr(max(0, a[i - 1].second - a[i].first));
hull.add(-2 * a[i].first, curB, i - 1);
auto [cost, id] = hull.query(a[i].second);
f[i] = {cost + sqr(a[i].second) + penalty, f[id].second + 1};
}
return f[n];
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
vector<pair<int, int>> a = {{-1, -1}};
for (int i = 0; i < n; i++)
a.push_back({min(r[i], c[i]), max(r[i], c[i]) + 1});
sort(begin(a), end(a));
int cur = 0;
for (int i = 1; i <= n; i++)
if (a[i].first == a[cur].first) a[cur].second = a[i].second;
else if (a[i].second > a[cur].second) a[++cur] = a[i];
n = cur;
a.resize(n + 1);
long long low = 0, high = 1e12, res = high;
while (low <= high)
{
long long mid = (low + high) / 2;
if (solve(a, mid).second > k) low = mid + 1;
else
{
res = mid;
high = mid - 1;
}
}
auto [f, photo] = solve(a, res);
return f - k * res;
}
