#include "aliens.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
using pf32 = pair<float, float>;
using pf64 = pair<double, double>;
using pf80 = pair<long double, long double>;
using vf32 = vector<float>;
using vf64 = vector<double>;
using vf80 = vector<long double>;
using vpf32 = vector<pf32>;
using vpf64 = vector<pf64>;
using vpf80 = vector<pf80>;
using vvf32 = vector<vf32>;
using vvf64 = vector<vf64>;
using vvf80 = vector<vf80>;
using vvpf32 = vector<vpf32>;
using vvpf64 = vector<vpf64>;
using vvpf80 = vector<vpf80>;
using fl80_t = long double;
template <typename key, typename val>
using ord_map = tree<key, val, less<key>, rb_tree_tag,
tree_order_statistics_node_update>;
template <typename key>
using ord_set = tree<key, null_type, less<key>, rb_tree_tag,
tree_order_statistics_node_update>;
#pragma endregion
struct line_t
{
int64_t k, m, p;
bool operator<(const line_t &o) const { return k < o.k; }
bool operator<(int64_t x) const { return p < x; }
long long eval(long long x) const { return k * x + m; }
};
struct cht_t
{
deque<line_t> hull;
int64_t div(int64_t a, int64_t b)
{
return floor(double(a) / b);
}
bool intersect(line_t &x, const line_t &y)
{
if (x.k == y.k)
{
x.p = x.m > y.m ? INT64_MAX : INT64_MIN;
}
else
{
x.p = div(y.m - x.m, x.k - y.k);
}
return x.p >= y.p;
}
void add(long long k, long long m)
{
line_t line = {k, m, 0};
// wtf?
while (hull.size() >= 2 &&
(intersect(line, hull.back()),
intersect(hull.back(), hull[(int)hull.size() - 2]),
line.p < hull.back().p))
{
hull.pop_back();
}
hull.push_back(line);
}
int64_t query(int64_t x)
{
if (!hull.size())
{
return INT64_MAX;
}
while (hull.size() >= 2 && hull[0].eval(x) >= hull[1].eval(x))
{
hull.pop_front();
}
return hull[0].eval(x);
}
};
void insert(int64_t left, int64_t tiles, cht_t &cht)
{
int64_t slope = 2 - 2 * left;
int64_t offset = (left - 1) * (left - 1) + tiles;
cht.add(slope, offset);
}
int64_t query(int64_t val, cht_t &cht)
{
int64_t y = cht.query(val);
return (y == INT64_MAX) ? INT64_MAX : y + val * val;
}
int64_t cost(p64 range)
{
assert(range.first <= range.second);
return (range.second - range.first + 1) * (range.second - range.first + 1);
}
long long take_photos(int n, int m, int k, vi32 r, vi32 c)
{
vp32 range(n);
for (int i = 0; i < n; i++)
{
if (c[i] > r[i])
{
swap(c[i], r[i]);
}
range[i] = {c[i], r[i]};
}
sort(range.begin(), range.end(),
[](p32 a, p32 b)
{
return (a.first == b.first) ? a.second > b.second : a.first < b.first;
});
int cur_max = -1;
vp32 selected;
for (auto &r : range)
{
if (r.second > cur_max)
{
selected.push_back(r);
cur_max = r.second;
}
}
vvi64 tile(selected.size(), vi64(k + 1, INT64_MAX));
vector<cht_t> cht(k + 1);
tile[0][1] = cost(selected[0]);
insert(selected[0].first, 0, cht[1]);
for (size_t point = 1; point < tile.size(); point++)
{
for (size_t count = 1; count <= min(point + 1, size_t(k)); count++)
{
int64_t &cur = tile[point][count];
int64_t &prev = tile[point - 1][count - 1];
p32 a = selected[point];
p32 b = selected[point - 1];
cur = min(cur, query(a.second, cht[count]));
if (prev != INT64_MAX)
{
int64_t val = prev + cost(a);
if (a.first <= b.second)
{
val -= cost({a.first, b.second});
}
cur = min(cur, val);
}
if (cur != INT64_MAX)
{
int64_t tiles = tile[point - 1][count - 1];
if (a.first <= b.second)
{
tiles -= cost({a.first, b.second});
}
insert(a.first, tiles, cht[count]);
}
}
}
int64_t result = *min_element(tile.back().begin(), tile.back().end());
return result;
}
