#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 CHT{
private:
deque<array<ll,3>>dq;
ll floor_div(ll x,ll y){
if(x>=0)return x/y;
return x/y-(x%y?1:0);
}
bool need(array<ll,3>l1,array<ll,3>l2,array<ll,3>add){
return double(l2[1]-l1[1])/(l1[0]-l2[0])<double(add[1]-l2[1])/(l2[0]-add[0]);
}
public:
CHT():dq(){}
void add(ll a,ll b,ll id){
array<ll,3>l{a,b,id};
while(dq.size()>=2&&!need(dq[dq.size()-2],dq[dq.size()-1],l)){
dq.pop_back();
}
dq.emplace_back(l);
}
pair<ll,ll>get(ll x){
if(dq.empty())return {inf,0};
while(dq.size()>=2&&dq[0][0]*x+dq[0][1]>dq[1][0]*x+dq[1][1]){
dq.pop_front();
}
return pair<ll,ll>{dq[0][0]*x+dq[0][1],dq[0][2]};
}
};
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 idx(n);iota(all(idx),0);
sort(all(idx),[&](ll i,ll j){return (r[i]!=r[j]?r[i]<r[j]:c[i]>c[j]);});
vector<pair<ll,ll>>v;
for(auto i:idx){
if(v.empty()||v.back().second<=c[i]){
v.emplace_back(r[i],c[i]+1);
}
}
n=v.size();
chmin(k,n);
auto cost=[&](ll i,ll j)->ll {
if(i==j)return 0;
if(j==0)return 0;
return (v[j-1].second-v[i].first)*(v[j-1].second-v[i].first)-(i>0&&v[i-1].second>=v[i].first?(v[i-1].second-v[i].first)*(v[i-1].second-v[i].first):0);
};
auto f=[&](ll lambda)->pair<ll,ll> {
vector<pair<ll,ll>>dp(n+1,{inf,inf});
dp[0]={0,0};
CHT cht;
cht.add(-2*v[0].first,v[0].first*v[0].first,0);
rep(i,1,n+1){
auto [val,id]=cht.get(v[i-1].second);
val+=v[i-1].second*v[i-1].second+lambda;
dp[i]=pair<ll,ll>{val,id+1};
if(i<n)cht.add(-2*v[i].first,val+v[i].first*v[i].first-(v[i-1].second>=v[i].first?(v[i-1].second-v[i].first)*(v[i-1].second-v[i].first):0),id+1);
}
return dp[n];
};
ll ng=-1,ok=(ll)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);
ll ans=val-ok*k;
tie(val,x)=f(ng);
chmax(ans,val-ng*k);
return ans;
}
