#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ld long double
const int maxn = 1e5 + 20;
const int maxk = 1e2 + 20;
int l[maxn] , r[maxn];
ll a[maxn] , b[maxn] , dp[maxn][maxk];
ll t2(int x)
{
return 1LL * x * x;
}
vector<int> hull;
int pt;
ld IS(int i , int j)
{
return (b[i] - b[j]) / (ld)(a[i] - a[j]);
}
void add(int i , int j)
{
a[i] = -2 * l[i + 1];
b[i] = dp[i][j - 1] + t2(l[i + 1]) - t2(max(0 , r[i] - l[i + 1]));
int sz = hull.size();
while(sz > 1 && IS(hull[sz - 2] , hull[sz - 1]) >= IS(hull[sz - 1] , i))
{
hull.pop_back();
sz--;
}
hull.pb(i);
}
ll f(int ind , int x)
{
return a[ind] * x + b[ind];
}
ll get(int x)
{
while(pt + 1 < (int)hull.size() && f(hull[pt] , x) >= f(hull[pt + 1] , x))
pt++;
return f(hull[pt] , x);
}
long long take_photos(int n, int m, int k, vector<int> R, vector<int> C)
{
m = m;
vector<pair<int , int> > tmp;
for(int i = 0; i < n; i++)
{
l[i] = min(R[i] , C[i]) , r[i] = max(R[i] , C[i]);
tmp.pb({r[i] , -l[i]});
}
sort(tmp.begin() , tmp.end());
for(int i = 0; i < n; i++)
{
l[i] = -tmp[i].second;
r[i] = tmp[i].first;
}
tmp.clear();
int mn = 1e9;
for(int i = n - 1; i >= 0; i--)
if(mn > l[i])
{
mn = l[i];
tmp.pb({l[i] , r[i]});
}
reverse(tmp.begin() , tmp.end());
n = tmp.size();
for(int i = 1; i <= n; i++)
l[i] = tmp[i - 1].first , r[i] = tmp[i - 1].second + 1;
r[0] = l[0] = -1;
memset(dp , 63 , sizeof dp);
memset(dp[0] , 0 , sizeof dp[0]);
for(int j = 1; j <= k; j++)
{
hull.clear();
pt = 0;
for(int i = 1; i <= n; i++)
{
add(i - 1 , j);
dp[i][j] = get(r[i]) + t2(r[i]);
//min(dp[i][j] , dp[lx][j - 1] + t2(l[lx + 1]) + t2(r[i]) - t2(max(0 , r[lx] - l[lx + 1])));
// shib = l[lx + 1]
}
}
return dp[n][k];
}
