#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
int reik[1001][1001] = {0};
void pad(int e, int s){
if(e > s) swap(e, s);
for(int i = e; i <= s; i++){
for(int j = e; j <= s; j++){
reik[i][j] = 1;
}
}
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
if(n == k){
for(int i = 0; i < n; i++){
pad(r[i], c[i]);
}
int ret = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < m; j++){
ret += reik[i][j];
}
}
return ret;
}else{ // r_i = c_i visada
vector<int> vec;
for(int i = 0; i < n; i++){
vec.push_back(r[i]);
}
sort(vec.begin(), vec.end());
// padalinu i k grupiu, kad galu skirtumu kvadratu suma butu kuo mazesne!
long long dp[n+1][k+1];
long long inf = 1e18;
for(int i = 0; i <= n; i++) for(int j = 0; j <= k; j++) dp[i][j] = inf;
dp[0][1] = 0;
for(int i = 0; i < n; i++) dp[i][1] = 1ll * (vec[i] - vec[0] + 1) * 1ll * (vec[i] - vec[0] + 1);
long long ans = dp[n-1][1];
for(int i = 1; i < n; i++){
for(int j = 2; j <= k; j++){ // koks ats, jei sitas uzbagia pref[i] ir naudota is viso j grupiu
for(int h = 0; h < i; h++){
dp[i][j] = min(dp[i][j], dp[h][j-1] + 1ll * (vec[i]-vec[h+1] + 1) * 1ll * (vec[i]-vec[h+1]+1));
}
if(i == n-1) ans = min(ans, dp[i][j]);
}
}
return ans;
}
}
