#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
struct CHT{
deque<pair<long long,int>> lines;
deque<long long> times;
deque<int> cnt;
long long intersect(pair<long long,int> line1, pair<long long,int> line2){
return (line2.first - line1.first + (line1.second - line2.second)) / (line1.second - line2.second);
}
void add_line(pair<long long,int> line,int num){
long long opt = 0;
while(lines.size()){
opt = max(opt,intersect(lines.back(),line));
if(opt <= times.back()){
lines.pop_back();
times.pop_back();
cnt.pop_back();
}
else break;
}
lines.push_back(line);
times.push_back(opt);
cnt.push_back(num);
}
pair<long long,int> get(int x){
while(times.size() > 1 && times[1] <= x){
times.pop_front();
lines.pop_front();
cnt.pop_front();
}
return {lines[0].first + (long long) x * lines[0].second,cnt[0]};
}
};
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c){
vector<pair<long long,long long>> points;
for(int i = 0;i<n;i++){
if(r[i] < c[i])
swap(r[i],c[i]);
points.push_back({r[i],c[i]});
}
sort(points.begin(),points.end(),[&](pair<int,int> a,pair<int,int> b){
if(a.first == b.first)
return a.second > b.second;
return a.first < b.first;
});
vector<pair<long long,long long>> tmp;
for(auto u:points){
while(tmp.size() && tmp.back().second >= u.second){
tmp.pop_back();
}
tmp.push_back(u);
}
points = tmp;
// for(auto u:points){
// cerr << u.first << ' ' << u.second << endl;
// }
n = points.size();
function<pair<int,long long>(long long)> get = [&](long long C){
// cout << C << endl;
CHT vals;
vector<long long> dp(n+1);
vector<int> cnt(n+1);
for(int i = 1;i<=n;i++){
long long val = dp[i-1] + points[i-1].second * points[i-1].second - 2*points[i-1].second;
if(i > 1)
val -= max(0ll,points[i-2].first - points[i-1].second + 1) * max(0ll,points[i-2].first - points[i-1].second + 1);
vals.add_line({val,-2*points[i-1].second},cnt[i-1]);
auto x = vals.get(points[i-1].first);
dp[i] = x.first + points[i-1].first * points[i-1].first + 2 * points[i-1].first + 1 + C;
cnt[i] = x.second + 1;
// long long tmp = dp[i];
// dp[i] = 2e18;
// for(int j = 0;j<i;j++){
// long long extra = 0;
// if(j > 0)
// extra -= max(0ll,points[j-1].first - points[j].second + 1) * max(0ll,points[j-1].first - points[j].second + 1);
// // cout << j << ' ' << extra << endl;
// long long num = dp[j] + (points[i-1].first - points[j].second + 1) * (points[i-1].first - points[j].second + 1) + extra + C;
// if(num < dp[i]){
// dp[i] = num;
// cnt[i] = cnt[j] + 1;
// }
// }
// assert(tmp == dp[i]);
}
return make_pair(cnt[n],dp[n] - k * C);
};
long long tl = 0,tr = (long long)m * m;
while(tl < tr){
long long tm = (tl + tr)/2;
if(get(tm).first <= k){
tr = tm;
}
else tl = tm + 1;
}
return get(tl).second;
}
