#include <bits/stdc++.h>
using namespace std;
typedef pair<long long,long long> P;
P arr[100000];
P temp[100000];
long long dp[100005]; //dp[i][j] : minimum grid to fill if we should take a picture unitl i-th place with j pictures.
const long long INF=1e18;
long long n,m,k;
int sz=0;
int ind=0;
struct Line {
long long a,b;
};
struct Fraction {
long long up,down;
};
Fraction cross(Line one,Line two) {
if (one.a<two.a) {
swap(one,two);
}
return {two.b-one.b,one.a-two.a};
}
bool cmp(Fraction one,Fraction two) {
__int128 ou=one.up;
__int128 od=one.down;
__int128 tu=two.up;
__int128 td=two.down;
return ou*td<tu*od;
}
Line line[100513];
void insert(Line l) {
if (sz>=1&&line[sz-1].a==l.a) {
if (l.b>line[sz-1].b) {
line[sz-1]=l;
}
return;
}
while (sz>1) {
Fraction before=cross(line[sz-2],line[sz-1]);
Fraction now=cross(line[sz-1],l);
if (cmp(before,now)) {
break;
}
sz--;
}
line[sz++]=l;
}
long long cost(int l,int r) {
long long minus=0;
if (l!=0&&arr[l-1].second-arr[l].first+2>0) {
minus=(arr[l-1].second-arr[l].first+2)*(arr[l-1].second-arr[l].first+2);
}
long long ret=(arr[r].second-arr[l].first+2)*(arr[r].second-arr[l].first+2);
ret-=minus;
return ret*2;
}
long long value;
int cut;
void getans(long long pen) {
sz=0;
ind=0;
for(int i=0;i<n;i++) {
if (i>0) {
long long minus=0;
if (arr[i-1].second-arr[i].first+2>0) {
minus=(arr[i-1].second-arr[i].first+2)*(arr[i-1].second-arr[i].first+2);
}
insert({-4*arr[i].first,2*arr[i].first*arr[i].first-8*arr[i].first-minus*2+dp[i-1]+pen});
}
else {
insert({-4*arr[i].first,2*arr[i].first*arr[i].first-8*arr[i].first+pen});
}
while (ind+1<sz&&cmp(cross(line[ind],line[ind+1]),{arr[i].second,1})) {
ind++;
}
long long val;
if (ind>=sz) {
val=INF;
}
else {
val=line[ind].a*arr[i].second+line[ind].b+2*(arr[i].second+2)*(arr[i].second+2);
}
dp[i]=val;
}
int now=n-1;
int cnt=0;
while (now!=-1) {
for(int i=now;i>=0;i--) {
long long val;
if (i==0) {
val=0;
}
else {
val=dp[i-1];
}
if (val+cost(i,now)+pen==dp[now]) {
now=i-1;
cnt++;
break;
}
if (i==0) {
printf(".\n");
now=-1;
}
}
}
value=dp[n-1];
cut=cnt;
}
bool comp(P a,P b) {
if (a.second==b.second) {
return a.first<b.first;
}
return a.second<b.second;
}
long long take_photos(int nn,int mm,int kk,vector<int> r,vector<int> c) {
n=nn;
m=mm;
k=kk;
for(int i=0;i<n;i++) {
if (r[i]>c[i]) {
swap(r[i],c[i]);
}
temp[i]=P(2*r[i]+1,2*c[i]+1);
}
sort(temp,temp+n,comp);
int s=0;
long long mini=1e8;
for(int i=n-1;i>=0;i--) {
if (temp[i].first<mini) {
arr[s++]=temp[i];
}
mini=min(mini,temp[i].first);
}
n=s;
reverse(arr,arr+n);
long long lo=-1;
long long hi=8*m*m+13; //(lo,hi]
while (lo+1<hi) {
long long mid=lo+(hi-lo)/2;
getans(2*mid+1);
if (k<=cut) {
lo=mid;
}
else {
hi=mid;
}
}
getans(2*hi);
if ((value-2*k*hi)%8!=0) {
return r[-1000000];
}
return (value-2*k*hi)/8;
}
