#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vector<vector<long long>>arr(m + 1);
for (long long i = 0;i<n;++i){
r[i]--;
c[i]--;
if (c[i] > r[i])swap(r[i],c[i]);
long long temp = (r[i] - c[i]);
if (temp % 2 == 1){
long long row = temp;
long long col = m - temp;
long long dist = max(abs(r[i] - row),abs(c[i] - col));
arr[temp].push_back(dist - 1);
}
else{
long long row = temp - 1;
long long col = m - row;
long long dist = max(abs(r[i] - row),abs(c[i] - col));
if (dist - 1 <= temp - 1)
arr[temp - 1].push_back(dist - 1);
row = temp + 1;
col = m - row;
dist = max(abs(r[i] - row),abs(c[i] - col));
if (dist - 1 <= temp + 1){
arr[temp + 1].push_back(dist - 1);
}
}
}
for (long long i = 0;i<=m;++i)sort(arr[i].begin(),arr[i].end());
vector<pair<long long,long long>>dp(m + 1,{0,0});
for (long long i = 0;i<m;++i){
long long dist = 0;
if (!arr[i].empty()){
dist = arr[i].back();
}
auto temp = dp[i - dist];
long long p = (long long)arr[i].size();
long long total = dist * dist * 4;
if (dp[i + dist].first < p + temp.first){
dp[i + dist].first = p + temp.first;
dp[i + dist].second = total + temp.second;
}
else if (dp[i + dist].first == p + temp.first && dp[i + dist].second > temp.second + total){
dp[i + dist].first = p + temp.first;
dp[i + dist].second = total + temp.second;
}
}
long long ans = m * m;
for (long long i = 0;i<=m;++i){
if (dp[i].first == n){
ans = min(ans,dp[i].second);
}
}
return ans;
}
