#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
struct Line{
long long m,c;
Line(long long M,long long C){
m=M;
c=C;
}
long long get(long long x){
return m*x+c;
}
double inter(Line l2){
double x=l2.c-c,y=m-l2.m;
return x/y;
}
};
vector<Line> ch;
bool cmp(Line x,Line y,Line z){
return x.inter(y)<y.inter(z);
}
void add(Line x){
while(ch.size()>1&&!cmp(ch[ch.size()-2],ch.back(),x))ch.pop_back();
ch.push_back(x);
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vector<pair<int,int>> tm,st;
for(int i=0;i<n;i++){
if(r[i]>c[i])swap(r[i],c[i]);
tm.push_back({r[i],c[i]});
}
sort(tm.begin(),tm.end(),[](pair<int,int> p1,pair<int,int> p2){
if(p1.first!=p2.first)return p1.first<p2.first;
return p1.second>p2.second;
});
st.push_back({-1,-1});
for(auto p:tm){
if(p.second>st.back().second)st.push_back(p);
}
n=st.size()-1;
long long dp[n+1][k+1],a[n+1],h[n+1];
for(int i=0;i<=n;i++){
a[i]=st[i].second+1;
h[i]=st[i].second-st[i].first+1;
}
for(int i=1;i<=n;i++)dp[i][0]=1e18;
for(int i=0;i<=k;i++)dp[0][i]=0;
for(int j=1;j<=k;j++){
ch.clear();
int idx=0;
for(int i=1;i<=n;i++){
long long x=-a[i]+h[i],y=max(0LL,a[i-1]-a[i]+h[i]),m=2*x,c=dp[i-1][j-1]-y*y+x*x;
add(Line(m,c));
idx=min(idx,(int)ch.size()-1);
while(idx+1<ch.size()&&ch[idx].inter(ch[idx+1])<a[i])idx++;
dp[i][j]=ch[idx].get(a[i])+a[i]*a[i];
}
}
return dp[n][k];
}
