#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) {
if(n<=50 && m<=100 && k==n) //First Subtask
{
int sol = 0;
vector<vector<int> > matrix;
matrix.resize(m);
for(int i = 0;i<m;i++)
matrix[i].resize(m);
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
matrix[i][j] = 0;
for(int i = 0;i<n;i++)
{
if(matrix[r[i]][c[i]]) continue;
int m = min(r[i],c[i]);
int M = max(r[i],c[i]);
for(int j = m;j<=M;j++)
for(int t = m;t<=M;t++)
matrix[j][t] = 1;
}
for(int i = 0;i<m;i++)
for(int j=0;j<m;j++)
sol+=matrix[i][j];
return sol;
}
bool flag = true;
for(int i = 0;i<n;i++)
if(r[i]!=c[i])
{
flag = false;
break;
}
if(n<=500 && m<=1000 && flag)
{
vector<pair<int,int> > obj;
for(int i = 0;i<n;i++)
obj.emplace_back(r[i],c[i]);
sort(obj.begin(),obj.end());
vector<vector<int> > dp;
dp.resize(n);
for(int i=0;i<n;i++)
{
dp[i].resize(k+1);
for(int j=0;j<=k;j++)
dp[i][j] = INT_MAX;
}
for(int i = 0;i<n;i++)
{
for(int j = 0;j<=i;j++) {
for (int t = 1; t <= k; t++) {
int area = (obj[i].first - obj[j].first + 1) * (obj[i].second - obj[j].second + 1);
int f;
if (j == 0 && t==1) f = 0;
else
if(t!=1) f=INT_MAX;
else f = dp[j - 1][t-1];
if(f==INT_MAX) continue;
dp[i][t] = min(dp[i][t], f + area);
}
}
}
int sol = INT_MAX;
for(int j=1;j<=k;j++)
sol=min(sol,dp[n-1][j]);
return sol;
}
return 0;
}
