#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define COL first
#define ROW second
pair<ll,ll> calc(int n, int m, vector<pair<ll,ll>>& pts, ll cost)
{
vector<ll> dp(n), cnt(n);
for (int i = 0; i < n; i++)
{
dp[i] = (pts[i].COL - pts[0].ROW + 1) * (pts[i].COL - pts[0].ROW + 1) + cost;
cnt[i] = 1;
for (int j = 0; j < i; j++)
{
ll new_square = (pts[i].COL - pts[j+1].ROW + 1);
ll overlap = max(pts[j].COL - pts[j+1].ROW + 1, 0LL);
ll total_area = new_square * new_square - overlap * overlap;
if (make_pair(dp[j] + total_area + cost, 1 + cnt[j]) <= make_pair(dp[i], cnt[i]))
{
dp[i] = dp[j] + total_area + cost;
cnt[i] = 1 + cnt[j];
}
}
}
/*
cout << "with a cost of " << cost << " we use " << cnt[n-1] << " squares for a total of " << dp[n-1] << '\n';
*/
return {cnt[n-1], dp[n-1]};
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
vector<pair<ll,ll>> pts(n);
for (int i = 0; i < n; i++)
{
if (r[i] > c[i])
swap(r[i], c[i]);
pts[i] = {c[i], r[i]};
}
sort(pts.begin(), pts.end());
vector<pair<ll,ll>> monotone;
for (int i = 0; i < n; i++)
{
while (monotone.size() > 0 && monotone.back().ROW >= pts[i].ROW)
monotone.pop_back();
monotone.push_back(pts[i]);
}
n = monotone.size();
ll lo = 0, hi = 1e12, mid, res;
while (lo < hi)
{
mid = (lo + hi) / 2;
auto [count, mini] = calc(n, m, monotone, mid);
if (count <= k)
res = mid, hi = mid - 1;
else
lo = mid + 1;
}
auto [count, mini] = calc(n, m, monotone, res);
return mini - count * res;
}
/*
int main()
{
cout << take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6}) << '\n';
cout << take_photos(2, 6, 2, {1, 4}, {4, 1}) << '\n';
return 0;
}
*/
