#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
const long long inf=1e13,inff=1e18;
long long dp[MAXN];
int cnt[MAXN];
struct interval{
int l,r;
inline friend bool operator < (interval fr,interval sc){
if(fr.l==sc.l)return fr.r>sc.r;
return fr.l<sc.l;
}
}s[MAXN],w[MAXN];
int n,m,k,sz;
long long area(long long l,long long r){
if(l>r)return 0;
return (r-l+1)*(r-l+1);
}
long long cost(int l,int r){
return area(w[l].l,w[r].r) - area(w[l].l,w[l-1].r);
}
void solve(long long delta){
for(int i=1;i<=sz;i++){
dp[i]=inff;
for(int t=i;t>=1;t--){
if(dp[t-1]+cost(t,i)+delta<dp[i]){
dp[i]=dp[t-1]+cost(t,i)+delta;
cnt[i]=cnt[t-1]+1;
}else if(dp[t-1]+cost(t,i)+delta==dp[i] and cnt[t-1]+1<cnt[i]){
cnt[i]=cnt[t-1]+1;
}
}
}
}
long long bin(){
long long l=-1,r=inf,tt;
while(l+1<r){
tt=(l+r)/2;
solve(tt);
if(cnt[sz]>k){
l=tt;
}else{
r=tt;
}
}
solve(r);
if(cnt[sz]==k)return dp[sz]-cnt[sz]*r;
long long val2=dp[sz]-cnt[sz]*r;
int k2=cnt[sz];
solve(r-1);
long long val1=dp[sz]-cnt[sz]*(r-1);
int k1=cnt[sz];
return (long long) val1 + (k-k1)*(val2-val1)/(k2-k1);
}
long long take_photos(int N, int M, int K, vector<int> r, vector<int> c){
n=N; m=M; k=K;
for(int i=1;i<=n;i++){
s[i]={min(r[i-1],c[i-1])+1,max(r[i-1],c[i-1])+1};
}
sort(s+1,s+n+1);
for(int i=1;i<=n;i++){
if(sz>0 and s[i].r<=w[sz].r)continue;
sz++; w[sz]=s[i];
}
k=min(k,sz);
return bin();
}
/*int main(){
cout<<take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6})<<"\n";
return 0;
}*/
