#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define f first
#define s second
using namespace std;
#include "aliens.h"
using ll = long long;
using ii = pair<int,int>;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
vector<pair<ll,ll>>pareto;
ll eval(pair<ll,ll>x,ll y){return x.f*y + x.s;}
ll sq(ll x){return x*x;}
bool cross(pair<ll,ll>back,pair<ll,ll>mid,pair<ll,ll>front){
return (back.s-mid.s)*(front.f-mid.f)>(back.f-mid.f)*(front.s-mid.s);
}
pair<ll,ll> solve(ll lambda){
//CHT
deque<pair<pair<ll,ll>,ll>>lines={{{-2*pareto[0].f,sq(pareto[0].f)},0}};
int n = sz(pareto);
for(int i=0;i<n;++i){
auto [x,y] = pareto[i];++y;
while(sz(lines)>=2&&eval(lines[0].f,y)>eval(lines[1].f,y))lines.pop_front();
ll dpi = eval(lines[0].f,y) + sq(y) + lambda, qnt = lines[0].s+1;
if(i==n-1)return {dpi,qnt};
else{
dpi += sq(pareto[i+1].f) - sq(max(0ll,y-pareto[i+1].f));
pair<ll,ll>cur = {-2*pareto[i+1].f,dpi};
while(sz(lines)>=2&& cross(lines[sz(lines)-2].f,lines.back().f,cur))lines.pop_back();
lines.pb({cur,qnt});
}
}
return {0,0};
}
ll take_photos(int n, int m, int k, vector<int> r1, vector<int> c) {
vector<ii>v(n);
for(int i=0;i<n;++i){
if(r1[i]<=c[i])v[i] = {r1[i],c[i]};
else v[i] = {c[i],r1[i]};
}
sort(all(v));
for(int i=0;i<n;++i){
if(pareto.empty()||pareto.back().second<v[i].s){
if(!pareto.empty()&&pareto.back().first==v[i].f)pareto.pop_back();
pareto.push_back(v[i]);
}
}
//Lagrange opt.
ll l = 0, r = 1e12;//max delta = 1e12 porque m<=1e6, logo lambda <= 1e12
while(l<r){
ll md = (l+r)/2;
pair<ll,ll>cur = solve(md);
if(cur.s>k)l = md+1ll;
else r = md;
}
pair<ll,ll>res = solve(r);
ll ans = res.f - r*k;
return ans;
}
