#include "aliens.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N = 5e2 + 10;
const long long inf = 1e18;
long long dp[N][N] , val[N][N];
long long tav(int x)
{
if(x < 0)
return 0;
return 1LL * x * x;
}
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);
//cout << i << " " << 1 << " : " << dp[i][1] << endl;
}
for(int j = 2 ; j <= k ; j++) for(int i = 0 ; i < n ; i++)
{
dp[i][j] = inf;
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);
//cout << i << " " << j << " : " << dp[i][j] << endl;
}
return dp[n - 1][k];
}
