#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Line{
ll a, b;
int c;
Line(){}
Line(ll _a, ll _b, int _c): a(_a), b(_b), c(_c) {}
ll get(ll x){return a*x+b;}
};
long double cross(Line &f, Line &g){
return (long double)(f.b-g.b) / (g.a-f.a);
}
struct LineContainer{
vector<Line> st;
int pt;
void init(){
st.clear(); pt = 0;
}
void insert(ll a, ll b, int c){
Line L(a, b, c);
while(st.size()>=2){
int f = (int)st.size()-2, s = (int)st.size()-1;
if (cross(st[f], st[s]) >= cross(st[s], L)) st.pop_back();
else break;
}
if (pt>=(int)st.size()) pt = max((int)st.size()-1, 0);
st.push_back(L);
}
pair<ll, int> query(ll x){
while(pt < (int)st.size()-1){
if (cross(st[pt], st[pt+1]) < x) pt++;
else break;
}
return {st[pt].get(x), st[pt].c};
}
}LC;
vector<pair<int, int>> a;
vector<int> X, Y;
vector<pair<ll, int>> dp;
int calc(ll w){
int n = X.size();
LC.init();
dp.clear();
LC.insert(-X[0]*4, (ll)X[0]*X[0]*2, 0);
for (int i=0;i<n;i++){
dp.push_back(LC.query(Y[i]+1));
dp.back().first += (ll)(Y[i]+1) * (Y[i]+1)*2 + w;
dp.back().second++;
if (i==n-1) break;
LC.insert(-X[i+1]*4, dp[i].first+ (ll)X[i+1]*X[i+1]*2 - (ll)max(Y[i]+1-X[i+1], 0) * max(Y[i]+1-X[i+1], 0)*2, dp[i].second);
}
return dp.back().second;
}
bool comp(pair<int, int> &x, pair<int, int> &y){
if (x.first==y.first) return x.second > y.second;
return x.first < y.first;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
for (int i=0;i<n;i++){
if (r[i]<=c[i]) a.emplace_back(r[i], c[i]);
else a.emplace_back(c[i], r[i]);
}
sort(a.begin(), a.end(), comp);
for (int i=0;i<n;i++){
if (X.empty() || Y.back() < a[i].second){
X.emplace_back(a[i].first);
Y.emplace_back(a[i].second);
}
}
//for (int i=0;i<(int)X.size();i++) printf(" %d %d\n", X[i], Y[i]);
//return (ll)1e9 * X.size() + calc(0);
if (calc(0)<=k) return dp.back().first/2;
ll L = -1, R = 1e12 + 100, ans = 1e12 + 100;
while(L<=R){
ll M = (L+R)>>1;
if (calc(M*2+1)<k) R = M-1, ans = M;
else L = M+1;
}
calc(ans*2);
//calc(0);
//printf("%lld\n", dp.back().first);
return dp.back().first/2 - ans * k;
}
