#include "aliens.h"
#include <bits/stdc++.h>
#define N 50005
#define M 1000005
using namespace std;
int maxi[M];
int x[N],y[N];
long long dp[N];
long long ndp[N];
long long calc_len(long long a,long long b,long long c,long long d){
if(a > c || b > d)return 0;
return (c - a + 1) * (d - b + 1);
}
long long calc_intersection(long long a0,long long b0,long long c0,long long d0, long long a1,long long b1,long long c1,long long d1){
long long a2 = max(a0,a1);
long long b2 = max(b0,b1);
long long c2 = min(c0,c1);
long long d2 = min(d0,d1);
return calc_len(a2,b2,c2,d2);
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
for(int i = 0;i<m;i++){
maxi[i] = -1;
}
for(int i = 0;i<n;i++){
if(r[i] > c[i])swap(r[i],c[i]);
maxi[r[i]] = max(maxi[r[i]],c[i]);
}
vector<pair<int,int>> points;
for(int i = 0;i<m;i++){
if(maxi[i] == -1)continue;
if(points.empty() || maxi[i] > points.back().second){
points.push_back({i,maxi[i]});
}
}
n = points.size();
for(int i = 1;i<=n;i++){
x[i] = points[i-1].first + 1;
y[i] = points[i-1].second + 1;
//cout << i << "aaa "<< x[i] << " " << y[i] << endl;
}
for(int i = 0;i<=n;i++){
dp[i] = 2e18;
}
dp[0] = 0;
long long ans = 2e18;
for(int used = 1;used<=k;used++){
for(int i = 0;i<=n;i++){
ndp[i] = 2e18;
}
ndp[0] = 0;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=i;j++){
ndp[i] = min(ndp[i], dp[j-1] + calc_len(x[j],x[j],y[i],y[i]) - calc_intersection(x[j],x[j],y[i],y[i], x[j-1],x[j-1],y[j-1],y[j-1]) );
}
}
for(int i = 0;i<=n;i++){
dp[i] = ndp[i];
//cout << dp[i] << " ";
}
//cout << endl;
ans = min(ans,dp[n]);
}
return ans;
}
