#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
long long int mnsquares = 1000000000;
vector<int> r, c;
int n;
//tehere is no point having overlapping squares
//at every point on the diagonal we have 2 choices - start a square here or not
//if we do, try making the square any size between 1 and thew max
long long int dp(int k, int m, int covered, int idx, vector<int> got, int nogot){
if (k<0) return 100000000000;
if (k==0 || idx==m){
//if (got==0) return 100000000000;
if (nogot!=n) return 10000000000;
//cout << k << ' ' << idx << ' ' << covered << ' ' << n << ' ' << nogot << endl;
return covered;
//we made it pat the end
}
long long int ans = dp(k, m, covered, idx+1, got, nogot);
//i is size of photo
for (int i=0;i<=m-idx;i++){
if (i==0){
vector<int> newgot=got;
int nnogot=nogot;
for (int a=0;a<n;a++){
if (r[a]==idx && c[a]==idx){
if (newgot[a]==0) nnogot++;
newgot[a]=1;
}
else if (r[a]<idx && c[a]<idx && newgot[a]==0) return 100000000000000;
}
ans=min(ans, dp(k-1, m, covered+1, idx+1, newgot, nnogot));
continue;
}
vector<int> newgot=got;
int nnogot=nogot;
for (int a=0;a<n;a++){
if (r[a]>=idx && r[a]<=idx+i && c[a]>=idx && c[a]<=idx+i){
if (newgot[a]==0) nnogot++;
newgot[a]=1;
}
else if (r[a]<idx && c[a]<idx && newgot[a]==0) return 100000000000000;
}
ans=min(ans, dp(k-1, m, covered+((i+1)*(i+1)), idx+1, newgot, nnogot));
}
return ans;
}
long long int take_photos(int N, int m, int k, vector<int> R, vector<int> C){
n=N;
r=R;
c=C;
return dp(k, m, 0, 0, vector<int> (N, 0), 0);
}
