#include "aliens.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n';
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll Inf = 1e18;
const int N = 5e2 + 10;
const int K = N;
vector<ll> R, C;
int n, m, k;
ll dp[N][K];
ll Dup[N];
void Prep(){
ll r, c;
for(int i = 1; i < m; i++){
r = R[i]; c = C[i - 1];
if(c > r)
Dup[i] = (c - r) * (c - r);
}
//debug(Dup[1]);
}
void SolveN2K(){
memset(dp, 31, sizeof dp);
dp[0][1] = (C[0] - R[0]) * (C[0] - R[0]);
for(int i = 1; i < m; i++){
for(int j = 1; j <= i + 1; j++){
for(int la = 1; la <= i; la ++){
dp[i][j] = min(dp[i][j], dp[la - 1][j - 1] - Dup[la] + (C[i] - R[la]) * (C[i] - R[la]));
}
}
dp[i][1] = min(dp[i][1], (C[i] - R[0]) * (C[i] - R[0]));
}
}
ll take_photos(int _m, int _n, int _k, vector<int> _r, vector<int> _c) {
n = _n; k = _k;
for(int i = 0; i < _m; i++)
if(_r[i] > _c[i])
swap(_r[i], _c[i]);
vector<int> I(_m);
iota(all(I), 0);
sort(all(I), [&](int i, int j){
return pii(_r[i], -_c[i]) < pii(_r[j], -_c[j]);
});
int mx = -1;
for(int i : I){
if(_c[i] > mx){
mx = _c[i];
R.pb(_r[i]);
C.pb(_c[i] + 1);
}
}
m = R.size();
ll ans = Inf;
//cerr << "! " << m << '\n';
//for(int i = 0; i < m; i++) cerr << R[i] << ' ' << C[i] << '\n';
Prep();
SolveN2K();
k = min(k, m);
ans = dp[m - 1][k];
//for(int i = 1; i <= k; i++) ans = min(ans, dp[m - 1][i]);
return ans;
}
