#include "aliens.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define shib first
#define arz second
using namespace std;
const int N = 5e4 + 10 , K = 110 , M = 1e9;
const long long inf = 1e18;
long long dp[N][K] , val[N][K];
vector <pair<long long , pair<int , long long>>> cht;
long long tav(long long x)
{
if(x < 0)
return 0;
return 1LL * x * x;
}
void Reset()
{
cht.clear();
cht.push_back(make_pair(0 , make_pair(0 , inf)));
}
long long saghf(long long sor , long long mak)
{
if(mak < 0)
sor *= -1;
mak = abs(mak);
if(sor < 0)
return sor / mak;
return (sor + mak - 1) / mak;
}
long long insec(pair<int , long long> od , pair<int , long long> nw)
{
if(od.shib == nw.shib)
return(nw.arz < od.arz ? -M : M);
long long sor = nw.arz - od.arz , mak = od.shib - nw.shib;
return saghf(sor , mak);
}
void Add_line(pair<int , long long> ln)
{
while(!cht.empty())
{
long long pos = insec(cht.back().S , ln);
if(pos <= cht.back().F)
cht.pop_back();
else
{
cht.push_back(make_pair(pos , ln));
break;
}
}
if(cht.empty())
cht.push_back(make_pair(0LL , ln));
}
long long Get(long long val)
{
int pos = upper_bound(cht.begin() , cht.end() , make_pair(val , make_pair(M , inf))) - cht.begin() - 1;
return 1LL * val * cht[pos].S.shib + cht[pos].S.arz;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector <pair<int , int>> vec;
for(int i = 0 ; i < n ; i++)
{
if(r[i] > c[i])
swap(r[i] , c[i]);
vec.push_back(make_pair(r[i] , c[i]));
}
sort(vec.begin() , vec.end());
vector <pair<int ,int>> all;
all.push_back(vec[0]);
for(auto u : vec)
{
if(all.back().F == u.F)
{
all.pop_back();
all.push_back(u);
continue;
}
if(u.S > all.back().S)
all.push_back(u);
}
n = all.size();
for(int i = 0 ; i < n ; i++)
{
dp[i][1] = tav(all[i].S - all[0].F + 1);
if(i + 1 < n)
val[i][1] = dp[i][1] - tav(all[i].S - all[i + 1].F + 1) + tav(all[i + 1].F);
}
for(int j = 2 ; j <= k ; j++)
{
Reset();
for(int i = 0 ; i < n ; i++)
{
dp[i][j] = Get(all[i].S + 1);
/*for(int x = 0 ; x < i ; x++)
dp[i][j] = min(dp[i][j] , val[x][j - 1] - 2LL * (all[i].S + 1) * all[x + 1].F);*/
dp[i][j] += tav(all[i].S + 1);
dp[i][j] = min(dp[i][j] , dp[i][j - 1]);
if(i + 1 < n)
{
val[i][j] = dp[i][j] - tav(all[i].S + 1 - all[i + 1].F) + tav(all[i + 1].F);
Add_line({-2 * all[i + 1].F , val[i][j - 1]});
}
}
}
return dp[n - 1][k];
}
