#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--;
A[++T] = A[i];
}
N = T;
for(int i = 1; i <= N; i++){
R[i] = A[i].x;
C[i] = A[i].y;
}
}
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);
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++){
ll p = i % 2, q = (i - 1) % 2;
deque<Line> dq;
dq.push_back({-2 * R[1], R[1] * R[1] + max(0LL,-R[1]+1)*max(0LL,-R[1]+1)});
for(int j = 1; j <= N; j++){
while(dq.size() >= 2 && dq[0].f(C[i] + 1) >= dq[1].f(C[i] + 1)) dq.pop_front();
D[p][j] = dq[0].f(C[i] + 1);
D[p][j] += (C[i] + 1) * (C[i] + 1);
Line f = {-2 * R[j + 1], D[q][j] + R[j + 1] * R[j + 1] + max(0LL,C[j]-R[j+1]+1)*max(0LL,C[j]-R[j+1]+1)};
while(dq.size() >= 2 && X_cross(f, dq[dq.size() - 2]) >= X_cross(f, dq[dq.size() - 1])) dq.pop_front();
dq.push_back(f);
}
}
return D[K % 2][N];
}
