//#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
deque<pair<pll, int> > dq;
int o=0;
bool check (ll k, ll b){
int e=dq.size();
auto [k0,b0]=dq[e-1].F;
auto [k1,b1]=dq[e-2].F;
// k1 * x + b1 = k0 * x + b0
// (b0 - b1) / (k1 - k0)
// k1 * x + b1 = k * x + b
// (b - b1) / (k1 - k)
//
// k < k0 < k1
//
// (b - b1) / (k1 - k) > (b0 - b1) / (k1 - k0)
// (b - b1) * (k1 - k0) - (b0 - b1) * (k1 - k) > 0
return (b - b1) * (k1 - k0) - (b0 - b1) * (k1 - k) <= 0;
}
void add(ll k, ll b, int cnt){
while(dq.size()>1 && check(k, b))dq.pop_back();
dq.push_back({{k,b},cnt});
}
pii get(int i, ll x, ll C){
if(i==dq.size()){
return {1000000009, 1000000009};
}
auto [k,b]=dq[i].F;
// cout<<"[i, k, b, x]: "<<i<<" "<<dq.size()<<" "<<k<<" "<<b<<" "<<x<<endl;
return {k*x+b, dq[i].S};
}
void calc_dp(int n, vector<pll> v, vector<pll> &dp, ll C){
dp[0]={0,0};
add(v[0].F*-2, v[0].F*v[0].F, 0);
for (int i=1; i<=n; i++){
auto &[ans, cnt]=dp[i];
ll r=v[i-1].S;
ans=r*r+C;
// cout<<"[ans]: "<<ans<<endl;
cnt=1;
ll x=r;
o=min((int)dq.size()-1, o);
while(i>1 && get(o,x,C)>get(o+1,x,C)){
// cout<<"[get]: "<<get(o,x,C).F<<" "<<get(o,x,C).S<<endl;
// cout<<"[get]: "<<get(o+1,x,C).F<<" "<<get(o+1,x,C).S<<endl;
o++;
}
auto [ans0, cnt0]=get(o,x,C);
// cout<<"[o]: "<<o<<" "<<dq.size()<<" "<<ans0<<" "<<cnt0<<endl;
ans+=ans0;
cnt+=cnt0;
int s=v[i-1].F;
// if(i>1 && v[i-2].S>s)s=v[i-2].S;
dp[i]=min(dp[i], {dp[i-1].F+(r-s)*(r-s)+C, dp[i-1].S+1});
// cout<<"[i, ans, cnt, C]: "<<i<<" "<<ans<<" "<<cnt<<" "<<C<<endl;
if(i==n)continue;
ll l=v[i].F;
add(-2*l, ans + l*l - max((ll)0, r-l)*max((ll)0, r-l), cnt);
// dp + (r1-l)^2 - (r2-l)^2
// dp + r1*r1 + l*l - 2*r1*l - (r2-l)^2
// (-2*l) * r1 + (dp - l*l + (r-l)^2)
}
// for (auto [x, y]:dp){
// cout<<"[dp]: "<<x<<" "<<y<<endl;
// }
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
ll Ans=0;
vector<pll> v, V(n);
for (int i=0; i<n; i++){
if(c[i]<r[i])swap(r[i], c[i]);
V[i]={r[i], -c[i]};
}
sort(all(V));
ll rr=-1;
for (auto [l,r]:V){
r*=-1;
// cout<<r<<endl;
if(r>rr)v.pb({l,r+1});
rr=max(r, rr);
}
V.clear();
n=v.size();
// for (auto [l,r]:v){
// cout<<"[l, r]: "<<l<<" "<<r<<endl;
// }
ll L=0, R=1ll*m*m;
// L=49, R=49;
while(L<=R){
ll C=(L+R)>>1;
vector<pll> dp(n+1);
calc_dp(n, v, dp, C);
// cout<<"[C,K]: "<<C<<" "<<dp[n].S<<endl;
if(dp[n].S>k){
L=C+1;
}else{
Ans=dp[n].F;
// cout<<"[C, Ans]: "<<C<<" "<<Ans<<endl;
R=C-1;
}
dq.clear();
o=0;
}
// cout<<Ans<<" "<<Ans-L*k<<" "<<R<<" "<<L<<endl;
return Ans-L*k;
}
