#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
const int maxn=100010;
struct Section{
int l,r;
Section(int _l=0,int _r=0):l(_l),r(_r){}
inline bool operator<(const Section& rhs) const{
return l!=rhs.l?l<rhs.l:r>rhs.r;
}
inline bool operator==(const Section& rhs) const{
return l==rhs.l && r==rhs.r;
}
};
struct Line{
ll a,b;
int idx=0;
Line(ll _a=0,ll _b=0,int _idx=0):a(_a),b(_b),idx(_idx){}
} dq[maxn];
vector<Section> sec;
pli dp[maxn];
inline bool check(Line l1,Line l2,Line l3){
ll a1=l1.a,b1=l1.b;
ll a2=l2.a,b2=l2.b;
ll a3=l3.a,b3=l3.b;
return (__int128)(a2-a3)*(b3-b1)>(__int128)(b3-b2)*(a1-a3);
}
inline ll get_val(ll x,Line ln){
return ln.a*x+ln.b;
}
inline pli calc_dp(ll ext){
int head=0,rear=0;
dq[rear++]=Line(-2ll*sec[0].l,(ll)sec[0].l*sec[0].l,0);
for(int i=1;i<=(int)sec.size();i++){
while(head+1<rear && get_val(sec[i-1].r,dq[head])>get_val(sec[i-1].r,dq[head+1])) head++;
dp[i]=pli(get_val(sec[i-1].r,dq[head])+(ll)sec[i-1].r*sec[i-1].r+ext,dp[dq[head].idx].second+1);
if(i<(int)sec.size()){
Line ln=Line(-2ll*sec[i].l,(ll)sec[i].l*sec[i].l+dp[i].first-(sec[i-1].r>sec[i].l?(ll)(sec[i-1].r-sec[i].l)*(sec[i-1].r-sec[i].l):0ll));
while(head<rear && check(dq[rear-2],dq[rear-1],ln)) rear--;
dq[rear++]=ln;
}
}
return dp[(int)sec.size()];
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
for(int i=0;i<n;i++){
if(r[i]>c[i]) swap(r[i],c[i]);
sec.push_back(Section(r[i],c[i]+1));
}
sort(sec.begin(),sec.end());
sec.erase(unique(sec.begin(),sec.end()),sec.end());
int mx=-1,sz=0;
for(int i=0;i<(int)sec.size();i++){
if(sec[i].r>mx) sec[sz++]=sec[i],mx=sec[i].r;
}
sec.erase(sec.begin()+sz,sec.end());
k=min(k,(int)sec.size());
ll L=0,R=(ll)m*m+10;
while(L!=R){
ll mid=(L+R)>>1;
if(calc_dp(mid).second<=k) R=mid;
else L=mid+1;
}
return calc_dp(R).first-R*k;
}
