#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 5e3 + 20;
int l[maxn] , r[maxn];
ll dp[maxn][maxn];
ll t2(int x)
{
return 1LL * x * 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 i = 1; i <= n; i++)
for(int j = 1; j <= k; j++)
for(int lx = i - 1; lx >= 0; lx--)
dp[i][j] = min(dp[i][j] , dp[lx][j - 1] + t2(r[i] - l[lx + 1]) - t2(max(0 , r[lx] - l[lx + 1])));
return dp[n][k];
}
