#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
ll l, r;
Lin(ll a_, ll b_, ll l_ = -CINF, ll r_ = CINF): a(a_), b(b_), 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);
}
ll sq(ll x){return x*x;}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
m--; // suppress warning
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());
vector<pair<ll, ll>> a;
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();
vector<ll> dp(n, INF);
for(int h = 0; h < k; h++){
q.clear();
add(Lin(-2*a[0].first, sq(a[0].first)-2*a[0].first));
for(int i = 0; i < n-1; i++){
ll b = sq(a[i+1].first)-2*a[i+1].first - sq(max(0ll,a[i].second-a[i+1].first+1)) + dp[i];
add(Lin(-2*a[i+1].first, b));
}
vector<ll> dp2(n);
for(int i = 0; i < n; i++){
dp2[i] = sq(a[i].second+1) + qry(a[i].second);
}
dp = dp2;
}
return dp[n-1];
}
