#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct cht{
vector<pair<int,int>> lines;
vector<int> test;
void add(int m, int c){
lines.push_back({m,c});
}
int query(int x){
int ans=1e13;
for(int i=0;i<lines.size();i++){
ans=min(ans,lines[i].first*x+lines[i].second);
}
return ans;
}
};
long long take_photos(int32_t n, int32_t m, int32_t k, std::vector<int32_t> r, std::vector<int32_t> c) {
vector<int> dp(n+1,1e13),a(n+1,0),b(n+1,0),gc={0},gr={0};
vector<pair<int,int>> points;
deque<pair<int,int>> dq;
int tmp,ans=1e13;
for(int i=0;i<n;i++){
if(r[i]>c[i]){
swap(r[i],c[i]);
}
points.push_back({c[i],r[i]});
}
sort(points.begin(),points.end());
for(int i=0;i<points.size();i++){
while(!dq.empty()&&dq.back().second>=points[i].second){
dq.pop_back();
}
dq.push_back(points[i]);
}
for(int i=0;i<dq.size();i++){
gc.push_back(dq[i].first+1);
gr.push_back(dq[i].second+1);
}
for(int i=0;i<dq.size();i++){
if(gc[i]-gr[i+1]+1>=0){
a[i]=2-2*gr[i+1];
b[i]=(gc[i]+2-2*gr[i+1])*(-gc[i]);
}else{
a[i]=2-2*gr[i+1];
b[i]=(1-gr[i+1])*(1-gr[i+1]);
}
// cout << a[i] << ' ' << b[i] << '\n';
}
dp[0]=0;
for(int i=1;i<=k;i++){
cht now;
now.add(a[0],b[0]);
for(int j=1;j<=dq.size();j++){
tmp=gc[j]*gc[j]+now.query(gc[j]);
now.add(a[j],b[j]+dp[j]);
dp[j]=tmp;
// cout << dp[j] << " \n"[j==dq.size()];
}
ans=min(ans,tmp);
}
return ans;
}
