#include <bits/stdc++.h>
using namespace std;
#include "aliens.h"
typedef long long ll;
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll dp[1005][1005], mn[1000005];
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
swap(n, m);
for(int i=0;i<n;i++)mn[i] = 1e18;
for(int i=0;i<m;i++){
ll x = max(r[i], c[i]), y = min(r[i], c[i]);
mn[x] = min(mn[x], y);
}
for(ll i=0;i<n;i++){
if(mn[i] == 1e18){
if(i)for(int j=0;j<=k;j++)dp[i][j] = dp[i-1][j];
continue;
}
ll lol = mn[i];
dp[i][0] = 1e18;
for(int j=1;j<=k;j++){
dp[i][j] = 1e18;
lol = mn[i];
for(int x=i-1;x>=0;x--){
if(lol > mn[x]){
dp[i][j] = min(dp[i][j], dp[x][j-1] + (i - lol + 1) * (i - lol + 1) - (x - lol + 1) * (x - lol + 1));
lol = mn[x];
}
}
dp[i][j] = min(dp[i][j], (i - lol + 1) * (i - lol + 1));
}
}
return *min_element(dp[n-1], dp[n-1] + k + 1);
}
