#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;
#define int ll
const int inf=1e18;
int sq(int x) {
return x*x;
}
struct line {
int a,b;
int f(int x) {
return a*x+b;
}
line() {
a=0, b=inf;
}
line(int x, int y) {
a=x, b=y;
}
};
const int sz=1<<20;
struct sgt {
sgt *L, *R;
line ln;
sgt() {
L=R=NULL; ln=line();
}
sgt(line n) {
L=R=NULL; ln=n;
}
void add(int l, int r, line n) {
if (n.f(l)<=ln.f(l) && n.f(r)<=ln.f(r)) {
ln=n; return;
}
if (n.f(l)>=ln.f(l) && n.f(r)>=ln.f(r)) {
return;
}
if (r-l==1) return;
int m=(l+r)>>1;
if (!L) L=new sgt(ln);
if (!R) R=new sgt(ln);
L->add(l,m,n);
R->add(m,r,n);
}
void add(line n) {
add(0,sz,n);
}
int query(int l, int r, int x) {
if (r<=x || l>x) return inf;
int m=(l+r)>>1;
int f=ln.f(x);
int s=L?L->query(l,m,x):inf;
int t=R?R->query(m,r,x):inf;
return min({f,s,t});
}
int query(int x) {
return query(0,sz,x);
}
};
int take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c) {
vector<int> a(m,0);
forn(i,n) {
int x=r[i], y=c[i];
if (x<y) {
a[x]=max(a[x],y-x+1);
} else {
a[y]=max(a[y],x-y+1);
}
}
int x=-inf;
forn(i,m) {
if (!a[i]) continue;
if (a[i]+i<=x) a[i]=0;
else x=a[i]+i;
}
int z=0;
forn(i,m) z+=!!a[i];
if (z<=k) {
int ans=0;
int last=-1;
forn(i,m) {
if (!a[i]) continue;
if (last==-1) {
ans+=a[i]*a[i];
last=i;
continue;
}
if (last + a[last] >= i) {
ans += sq(a[i]) - sq(last+a[last]-i);
last=i;
} else {
ans+=a[i]*a[i];
last=i;
}
}
return ans;
}
if (n*k > 1e7) return -1;
vector<sgt> st(k+1);
vector<pi> v;
forn(i,m) if (a[i]) v.pb({i,i+a[i]});
n=v.size();
st[1].add({-2*v[0].f,sq(v[0].f)});
vector<int> dp(k+1,inf);
dp[1]=sq(v[0].s - v[0].f);
for (int i=1; i<n; ++i) {
for (int j=min(1ll*k,i+1); j>0; --j) {
int f=st[j].query(v[i].s) + sq(v[i].s);
int s=dp[j-1] + sq(v[i].s-v[i].f);
if (v[i-1].s > v[i].f) s-=sq(v[i-1].s-v[i].f);
dp[j]=min(f,s);
st[j].add({-2*v[i].f,sq(v[i].f)+s-sq(v[i].s-v[i].f)});
}
}
return dp[k];
}
#undef int
