#include "aliens.h"
#include<vector>
#include<algorithm>
#define x first
#define y second
#define DIM 100005
using namespace std;
int n, dq[DIM], num[DIM];
long long d[2][DIM];
pair<int, int> v[DIM];
pair<int, long long> w[DIM];
int cmp(pair<int, int> a, pair<int, int> b){
if(a.x == b.x){
return a.y > b.y;
}
return a.x < b.x;
}
long long calc(pair<int, long long> p, int i){
return p.y + p.x * 1LL * i;
}
long long det(pair<int, long long> p1, pair<int, long long> p2, pair<int, long long> p3){
return (p2.x - p1.x) * (p3.y - p1.y) - (p3.y - p1.y) * (p2.x - p1.x);
}
long long take_photos(int N, int m, int k, vector<int> r, vector<int> c) {
int i, ii, nr, t, p, u;
long long sol;
n = N;
for(i = 1; i <= n; i++){
v[i].x = min(r[i - 1], c[i - 1]);
v[i].y = max(r[i - 1], c[i - 1]);
}
sort(v + 1, v + n + 1, cmp);
nr = 1;
for(i = 2; i <= n; i++){
if(v[i].y > v[i - 1].y){
v[++nr] = v[i];
}
}
for(i = 1; i <= n; i++){
v[i].x--;
}
n = nr;
for(i = 1; i <= n; i++){
d[0][i] = (v[i].y - v[1].x) * 1LL * (v[i].y - v[1].x);
}
sol = d[0][n];
k = min(k, n);
t = 0;
for(ii = 2; ii <= k; ii++){
t = 1 - t;
p = u = 1;
w[1].x = -2 * v[ii].x;
w[1].y = v[ii].x * 1LL * v[ii].x + d[1 - t][ii - 1] - max(0LL, (v[ii - 1].y - v[ii].x) * 1LL * (v[ii - 1].y - v[ii].x) );
for(i = ii; i <= n; i++){
while(p < u && calc(w[p], v[i].y) > calc(w[p + 1], v[i].y) ){
p++;
}
d[t][i] = w[p].y + w[p].x * 1LL * v[i].y + v[i].y * 1LL * v[i].y;
if(i != n){
w[++u].x = -2 * v[i + 1].x;
w[u].y = d[t][i] + v[i + 1].x * 1LL * v[i + 1].x - max(0LL, (v[i].y - v[i + 1].x) * 1LL * (v[i].y - v[i + 1].x) );
while(p + 1 < u && det(w[u - 2], w[u - 1], w[u]) < 0){
u--;
w[u] = w[u + 1];
}
}
}
sol = min(sol, d[t][n]);
}
return sol;
}
