#include "aliens.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define orta ((ll)(bas+son)/2)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define inf 1000000000000
#define N 1000005
#define MOD 998244353
using namespace std;
struct line {
ll m;
ll c;
int id;
};
int n,m,k,sz;
ii p[N];
int ptr;
ll dp[N];
int cnt[N];
vector<line> lines;
ll sq(ll x) {return x*x;}
ll get(int ptr,ll x,ll c) {
return lines[ptr].m*x+lines[ptr].c+c;
}
double inter(line a,line b) {
return 1.0*(b.c-a.c)/(a.m-b.m);
}
void add_line(ll m,ll c,int id) {
line cur={m,c,id};
while(sz(lines)>1 && inter(lines.back(),cur)<=inter(lines[sz(lines)-2],cur)) {
lines.ppb();
}
lines.pb(cur);
umin(ptr,sz(lines)-1);
}
int solve(ll pen) {
lines.clear();
ptr=0;
p[0]={0,-1};
for(int i=1;i<=sz;i++) {
add_line(-2*(p[i].st-1),dp[i-1]+sq(p[i].st-1)-sq(max(0,p[i-1].nd-p[i].st+1))+pen,i);
while(ptr+1<sz(lines) && get(ptr,p[i].nd,sq(p[i].nd))>=get(ptr+1,p[i].nd,sq(p[i].nd))) ++ptr;
dp[i]=get(ptr,p[i].nd,sq(p[i].nd));
cnt[i]=cnt[lines[ptr].id-1]+1;
}
return cnt[sz];
}
long long take_photos(int d1, int d2, int d3, std::vector<int> r, std::vector<int> c) {
n=d1;
m=d2;
k=d3;
vector<ii> ps;
for(int i=0;i<n;i++) {
if(r[i]>c[i]) swap(r[i],c[i]);
ps.pb({r[i],-c[i]});
}
sort(ps.begin(),ps.end());
ps.erase(unique(ps.begin(),ps.end()),ps.end());
n=sz(ps);
for(int i=n-1;i>=0;i--) {
while(sz && -ps[i].nd>=p[sz].nd) --sz;
p[++sz]={ps[i].st,-ps[i].nd};
}
reverse(p+1,p+1+sz);
ll bas=1,son=inf;
while(bas<=son) {
if(solve(orta)<=k) son=orta-1;
else bas=orta+1;
}
solve(son);
return dp[sz]-k*son;
}
