#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e12+1;
const ll CINF = 1e6+1;
struct Lin{
ll a, b; // a*x+b
int cnt = 0;
ll l, r;
Lin(ll a_, ll b_, int cnt_ = 0, ll l_ = -CINF, ll r_ = CINF): a(a_), b(b_), cnt(cnt_), l(l_), r(r_) {}
ll eval(ll x) {return a*x+b;}
};
ll sect(Lin f1, Lin f2){
return (f2.b-f1.b) / (f1.a-f2.a);
}
deque<Lin> q;
void add(Lin f){
while(!q.empty() && q.back().eval(q.back().l) >= f.eval(q.back().l)) q.pop_back();
if(!q.empty()){
q.back().r = sect(q.back(), f);
f.l = q.back().r+1;
}
q.push_back(f);
}
ll qry(ll x){
while(x > q.front().r) q.pop_front();
return q.front().eval(x);
}
int cqry(ll x){
while(x > q.front().r) q.pop_front();
return q.front().cnt;
}
ll sq(ll x){return x*x;}
int n;
vector<pair<ll, ll>> a;
pair<ll, int> calc(ll lambda){
q.clear();
add(Lin(-2*a[0].first, sq(a[0].first)-2*a[0].first));
ll dp = -1;
int cnt = -1;
for(int i = 0; i < n; i++){
dp = sq(a[i].second+1) + qry(a[i].second) + lambda;
cnt = cqry(a[i].second)+1;
if(i < n-1){
ll b = sq(a[i+1].first)-2*a[i+1].first - sq(max(0ll,a[i].second-a[i+1].first+1)) + dp;
add(Lin(-2*a[i+1].first, b, cnt));
}
}
return {dp, cnt};
}
ll take_photos(int N, int m, int k, vector<int> r, vector<int> c){
n = N;
m--; // suppress warning
a.clear();
vector<pair<int, int>> v;
for(int i = 0; i < n; i++){
v.emplace_back(min(r[i], c[i]), -max(r[i], c[i]));
}
sort(v.begin(), v.end());
for(int i = 0; i < n; i++){
if(a.empty() || a.back().second < -v[i].second) a.emplace_back(v[i].first, -v[i].second);
}
n = (int)a.size();
ll lo = 0, hi = INF;
for(ll mid=(lo+hi)/2; lo<hi; mid=(lo+hi)/2){
auto [dp, cnt] = calc(mid);
if(cnt > k) lo = mid+1;
else hi = mid;
}
auto [dp, cnt] = calc(lo);
if(cnt > k) tie(dp, cnt) = calc(--lo);
ll ans = dp - k*lo;
return ans;
}
