#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
vector<ll>dp[100001];
const ll INF = 1e18;
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<int>h(m,m);
for(int i=0;i<n;i++){
int a = max(r[i],c[i]);
int b = min(r[i],c[i]);
h[a] = min(h[a],b);
}
int L = m;
vector<int>b;
for(int i=m-1;i>=0;i--){
if(h[i]==m)continue;
if(h[i]<L)b.push_back(i);
L = min(L,h[i]);
}
b.push_back(-1);
reverse(b.begin(),b.end());
n = b.size()-1;
//for(int x:b)cout<<x<<" ";
//cout<<'\n';
//for(int i=1;i<=n;i++)cout<<h[b[i]]<<" ";
//cout<<'\n';
for(int i=0;i<=n;i++){
dp[i].assign(k+1,INF);
}
dp[0][0] = 0;
//ri<=ri+1
//li<=li+1
for(int i=1;i<=n;i++){
for(int j=i-1;j>=0;j--){
for(int l=1;l<=k;l++){
if(dp[j][l-1] != INF){
ll len = b[i] - h[b[j+1]]+1;
len*=len;
if(j && b[j] >= h[b[j+1]]){
ll a = b[j] - h[b[j+1]]+1;
len-=a*a;
}
dp[i][l] = min(dp[i][l],dp[j][l-1] + len);
}
}
}
}
ll ans = INF;
for(int i=1;i<=k;i++)ans = min(ans,dp[n][i]);
return ans;
}
