#include "aliens.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
int n, m, k;
ll dp[101010][555];
p a[101010];
vector<p> v;
struct CHT{
struct Line{
ll a, b, c;
Line(ll a = 0, ll b = 0, ll c = 0) : a(a), b(b), c(c) {}
ll f(ll x){ return a * x + b; }
};
Line v[101010]; int pv, top;
ll f(int x, ll y){ return v[x].f(y); }
void init(){ pv = top = 0; }
int chk(const Line &a, const Line &b, const Line &c){
return (double)(a.b - b.b) / (b.a - a.a) >= (double)(c.b - b.b) / (b.a - c.a);
}
void update(Line l){
if(top > pv && v[top-1].a == l.a){
if(l.b > v[top-1].b) l = v[top-1]; top--;
}
while(top >= pv+2 && chk(v[top-2], v[top-1], l)) top--;
v[top++] = l;
}
p query(ll x){
while(pv+1 < top && v[pv].f(x) >= v[pv+1].f(x)) pv++;
return {v[pv].f(x), v[pv].c};
}
} cht;
void init(int N, int M, int K, const vector<int> &R, const vector<int> &C){
m = M, k = K; v.clear();
for(int i=0; i<N; i++) v.emplace_back(min(R[i], C[i]), max(R[i], C[i]) + 1);
sort(all(v), [](p a, p b){
if(a.y != b.y) return a.y < b.y;
return a.x > b.x;
});
n = 0;
for(auto &i : v){
while(n && a[n].x > i.x) n--;
a[++n] = i;
}
for(int i=1; i<=n; i++) dp[i][1] = (a[i].y - a[1].x) * (a[i].y - a[1].x);
}
ll take_photos(int N, int M, int K, vector<int> R, vector<int> C){
init(N, M, K, R, C);
int q = min(n, k);
for(int i=2; i<=q; i++){
cht.init(); cht.update(CHT::Line(-2*a[1].x, a[1].x * a[1].x, 0));
for(int j=1; j<=n; j++){
dp[i][j] = cht.query(a[j].y).x + a[j].y * a[j].y;
ll ta = a[j+1].x, tb = max(0LL, a[j].y - a[j+1].x);
ll aa = -2*a[j+1].x;
ll bb = dp[i-1][j] + ta*ta - tb*tb;
cht.update(CHT::Line(aa, bb, i));
}
}
return dp[q][n];
}
// g++ -O2 -std=c++11 -static -o main grader.cpp aliens.cpp aliens.h
