#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lf = long double;
#define x first
#define y second
ll N, M, K;
pair<ll, ll> A[100005];
ll R[100005];
ll C[100005];
ll D[2][100005];
void init(){
sort(A + 1, A + N + 1, [&](pair<ll, ll> a, pair<ll, ll> b) -> bool{
if(a.y != b.y) return a.y < b.y;
else return a.x > b.x;
});
ll T = 0;
for(int i = 1; i <= N; i++){
while(T && A[T].x >= A[i].x) T--;
if(A[T].y < A[i].y) R[++T] = A[i].x, C[T] = A[i].y;
}
N = T;
}
struct Line{
ll a, b, i;
ll f(ll x){
return a * x + b;
}
};
lf X_cross(Line f, Line g){
return 1.0 * (f.b - g.b) / (g.a - f.a);
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
N = n; M = m; K = k;
for(int i = 1; i <= n; i++){
A[i] = {r[i - 1], c[i - 1]};
A[i].x++; A[i].y++;
if(A[i].x > A[i].y){
swap(A[i].x, A[i].y);
}
}
init();
K = min(K, N);
vector<vector<ll>> D(K + 5, vector<ll>(N + 5, 1e18));
for(int i = 1; i <= N; i++){
D[1][i] = (C[i]-R[1]+1)*(C[i]-R[1]+1);
}
for(int i = 2; i <= K; i++){
for(int j = 1; j <= N; j++){
for(int k = 1; k <= i - 1; k++){
D[i][j] = min(D[i][j], D[i - 1][k] + (C[j-1]-R[k]+1)*(C[j-1]-R[k]+1) + max(0LL,C[k-1]-R[k]+1)*max(0LL,C[k-1]-R[k]+1));
}
}
}
return D[K][N];
}
