#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef struct point{
lld r, c;
point(lld r_, lld c_){
r = min(r_, c_);
c = max(r_, c_);
}
bool operator < (const point &other) const{
return c != other.c ? c < other.c : r > other.r;
}
} point;
vector<point> P, A;
int N = 0;
lld D[501][501];
const lld INF = 1LL<<62;
inline lld square (lld x) { return x * x; }
lld take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
for (int i=0; i<n; i++) P.push_back(point(r[i], c[i]));
sort(P.begin(), P.end());
for (int i=0; i<n; i++){
point p = P[i];
while (N){
if ((A.back()).r >= p.r){
--N;
A.pop_back();
}
else break;
}
A.push_back(p);
++N;
}
n = N;
k = min(k, n);
for (int i=0; i<n; i++){
for (int j=2; j<=k; j++) D[i][j] = INF;
}
for (int i=0; i<n; i++) D[i][1] = square(A[i].c - A[0].r + 1);
for (int l=1; l<k; l++){
for (int i=l-1; i<n-1; i++){
for (int j=i+1; j<n; j++){
lld val = D[i][l] + square(A[j].c - A[i+1].r + 1);
if (A[i+1].r <= A[i].c)
val -= square(A[i].c - A[i+1].r + 1);
D[j][l+1] = min(D[j][l+1], val);
}
}
}
return D[n-1][k];
}
