#include<bits/stdc++.h>
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,n) for(ll i=0;i<(ll)n;++i)
#define rep3(i,l,r) for(ll i=(ll)l;i<(ll)r;++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)a-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
static constexpr ll mod1=998244353;
static constexpr ll mod=1000000007;
static constexpr ll inf=numeric_limits<ll>::max()/2;
using vl=vector<ll>;
struct RMQ{
private:
int sz;
vector<ll>seg;
public:
RMQ(int n):sz(1){
while(sz<n)sz<<=1;
seg.resize(sz<<1,inf);
}
RMQ(const vector<ll>&v):sz(1){
while(sz<(int)v.size())sz<<=1;
seg.resize(sz<<1,inf);
rep(i,v.size())seg[i+sz]=v[i];
rrep(i,sz)seg[i]=min(seg[i<<1],seg[i<<1^1]);
}
ll prod(int l,int r)const{
l+=sz,r+=sz;
ll ret=inf;
while(l!=r){
if(l&1)chmin(ret,seg[l++]);
if(r&1)chmin(ret,seg[--r]);
l>>=1,r>>=1;
}
return ret;
}
};
ll take_photos(int n,int m,int k,vector<int>r,vector<int>c){
rep(i,n)if(r[i]>c[i])swap(r[i],c[i]);
vl v(m,inf);
rep(i,n)chmin(v[c[i]],r[i]);
RMQ rmq(v);
auto cost=[&](ll l,ll r)->ll {
ll mi=rmq.prod(l,r);
if(mi>=r)return 0LL;
return (r-mi)*(r-mi);
};
auto f=[&](ll lambda)->pair<ll,ll> {
vector<pair<ll,ll>>dp(m+1,{inf,inf});
dp[0]={0,0};
vl idx(m+1,0);
auto check=[&](ll l,ll r)->void {
const ll cst=cost(l,r);
if(cst==0){
if(chmin(dp[r],dp[l])){
idx[r]=l;
}
}
else if(chmin(dp[r],pair<ll,ll>{dp[l].first+cst+lambda,dp[l].second+1})){
idx[r]=l;
}
};
auto rec=[&](auto&&rec,ll l,ll r)->void {
if(r-l<=1)return;
ll mid=(l+r)/2;
rep(i,idx[l],idx[r]+1)check(i,mid);
rec(rec,l,mid);
rep(i,l,mid+1)check(i,r);
rec(rec,mid,r);
};
check(0,m);
rec(rec,0,m);
return dp[m];
};
ll ng=-1,ok=m*m+1;
while(ok-ng>1){
ll mid=(ok+ng)/2;
auto [val,x]=f(mid);
//cerr<<mid<<" "<<val<<" "<<x<<endl;
if(x>k)ng=mid;
else ok=mid;
}
auto [val,x]=f(ok);
return val-k*ok;
}
