#include "aliens.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e18;
int n,dp[501][501],s[100001],e[100001],mx[1000001];
vector <pair <int, int>> ve;
int f(int i, int j){
if (j<0)
return INF;
if (i==n)
return 0;
if (dp[i][j]!=-1)
return dp[i][j];
dp[i][j]=INF;
for (int k=i;k<n;k++){
int cost=(e[k]-s[i]+1)*(e[k]-s[i]+1);
if (s[k+1]<=e[k])
cost-=(s[k+1]-s[k]+1)*(s[k+1]-s[k]+1);
dp[i][j]=min(dp[i][j],f(k+1,j-1)+cost);
}
return dp[i][j];
}
long long take_photos(int32_t N, int32_t M, int32_t K, vector <int32_t> R, vector <int32_t> C){
memset(mx,-1,sizeof(mx));
memset(dp,-1,sizeof(dp));
for (int i=0;i<N;i++)
mx[min(R[i],C[i])]=max(mx[min(R[i],C[i])],(int)max(R[i],C[i]));
for (int i=0;i<M;i++)
if (mx[i]!=-1)
ve.emplace_back(i,mx[i]);
sort(ve.begin(),ve.end());
int cur=-1;
for (auto [i,j]:ve)
if (j>cur){
s[n]=i;
e[n]=j;
n++;
cur=j;
}
s[n]=INF;
return f(0,K);
}
