#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())
ll n, m, k;
pll a[100010];
ll dp[110][100010];
ll gyo[100010];
struct line
{
ll A, B;
ld S;
};
ld intersect(ll A1, ll B1, ll A2, ll B2)
{
if(A1 == A2)
assert(0);
return (ld)(B2 - B1) / (ld)(A1 - A2);
}
struct CHT
{
vector<line> lin;
void init(void)
{
lin.clear();
}
void update(ll X, ll Y)
{
while(!lin.empty())
{
if(intersect(lin.back().A, lin.back().B, X, Y) < lin.back().S)
lin.pop_back();
else
break;
}
if(lin.empty())
{
lin.push_back({X, Y, -INF});
return;
}
lin.push_back({X, Y, intersect(lin.back().A, lin.back().B, X, Y)});
}
ll query(ll X)
{
ll l = 0, r = (ll)lin.size() - 1;
while(l <= r)
{
ll mid = (l + r) >> 1;
if(lin[mid].S <= X)
l = mid + 1;
else
r = mid - 1;
}
return lin[r].A * X + lin[r].B;
}
}cht;
void solve(void)
{
for(ll i = 1 ; i <= n ; i++)
dp[0][i] = m * m + 1;
for(ll i = 1 ; i <= k ; i++)
{
cht.init();
cht.update(-2 * (a[1].fi - 1), (a[1].fi - 1) * (a[1].fi - 1));
for(ll j = 1 ; j <= n ; j++)
{
dp[i][j] = cht.query(a[j].se) + a[j].se * a[j].se;
if(j < n)
cht.update(-2 * (a[j + 1].fi - 1), dp[i - 1][j] + (a[j + 1].fi - 1) * (a[j + 1].fi - 1) - gyo[j]);
}
}
}
long long take_photos(int N, int M, int K, std::vector<int> R, std::vector<int> C)
{
vector<pll> vec;
n = N, m = M, k = K;
for(ll i = 0 ; i < n ; i++)
a[i + 1] = {R[i] + 1, C[i] + 1};
for(ll i = 1 ; i <= n ; i++)
{
if(a[i].fi > a[i].se)
swap(a[i].fi, a[i].se);
}
sort(a + 1, a + 1 + n);
for(ll i = 2 ; i <= n ; i++)
{
if(a[i].fi != a[i - 1].fi)
vec.push_back(a[i - 1]);
}
vec.push_back(a[n]);
ll maxx = 0;
n = 0;
for(auto &i : vec)
{
if(i.se > maxx)
{
maxx = i.se;
a[++n] = i;
}
}
for(ll i = 1 ; i < n ; i++)
{
ll w1 = a[i + 1].fi, w2 = a[i].se;
if(w2 < w1)
gyo[i] = 0;
else
gyo[i] = (w2 - w1 + 1) * (w2 - w1 + 1);
}
solve();
ll ans = INF;
for(ll i = 1 ; i <= k ; i++)
ans = min(ans, dp[i][n]);
return ans;
}
