#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL_MAX LONG_LONG_MAX
#define LL_MIN LONG_LONG_MIN
//#define INF 314159265358979323
#define speed ios_base::sync_with_stdio(false); cin.tie(0)
#define stMx(a,b) a = max(a,b)
#define stMn(a,b) a = min(a,b)
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
typedef vector<int> vi;
typedef set<int> si;
typedef vector<ii> vii;
typedef set<ii> sii;
#define REP(i, a, b) for(int i = a; i < b; i++)
#define float long double
deque<iii> dq;
int f(iii line, int x) {
return line.fi.fi * x + line.fi.se;
}
ii query(int x) {
while(dq.size() > 1) {
if(f(dq[0], x) < f(dq[1], x)) dq.pop_front();
else break;
}
return mp(f(dq[0], x),dq[0].se);
}
float intersect(int a, int b, int c, int d) {
return (float)(d - b) / (a - c);
}
float intersect(iii p1, iii p2) {
return intersect(p1.fi.fi, p1.fi.se, p2.fi.fi, p2.fi.se);
}
void ins(int m, int c, int idx) {
iii line = mp(ii(m, c),idx);
while(dq.size() > 1) {
int s = dq.size();
if(intersect(dq[s - 1], line) <= intersect(dq[s - 2], line)) dq.pop_back();
else break;
}
dq.push_back(line);
}
ii getCst(int n, vii &pts, int cst) {
ii dp[n];dp[0]=mp(0,0);
dq.clear();
REP(i,1,n){
// insert e line 4 i-1
ins(2*pts[i].fi,max((int)0,pts[i-1].se-pts[i].fi+1)*max((int)0,pts[i-1].se-pts[i].fi+1)+2*pts[i].fi-pts[i].fi*pts[i].fi-dp[i-1].fi,dp[i-1].se);
dp[i].fi=(pts[i].se+1)*(pts[i].se+1)-query(pts[i].se).fi+cst; dp[i].se=query(pts[i].se).se+1;
assert(dp[i].se>=dp[i-1].se);
}
return dp[n-1];
}
long long take_photos(int32_t n, int32_t m, int32_t k, std::vector<int32_t> r, std::vector<int32_t> c) {
ii pts[n];
REP(i,0,n)if(r[i]>c[i])swap(r[i],c[i]);
REP(i,0,n) pts[i]=mp(r[i],c[i]);
sort(pts,pts+n);
vector<ii> imptPts; imptPts.pb(mp(-10,-10));
REP(i,0,n) if(pts[i].se>imptPts.back().se) imptPts.pb(pts[i]);
int relN = imptPts.size(); //int dp[relN+1];
// dp[i][k]=min cst to take <=k photos of [1,i]
int l=-1,h=(int)m*(int)m;
while(h-l>1){
int lambda=(l+h)/2;
if(getCst(relN,imptPts,lambda).se<=(int)k)h=lambda;
else l=lambda;
}
return (long long)getCst(relN,imptPts,h).fi-(int)k*h;
}
