#include "aliens.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const int N = (int)1e5 + 123, inf = 1e9;
const ll INF = 1e18;
using namespace std;
ll sqr(ll x){
return x * x;
}
ll take_photos(int n, int m, int k, vector<int> row, vector<int> col) {
vector< pii > arr, arr2;
for(int i = 0; i < n; i++){
int l, r;
l = row[i];
r = col[i];
if(l > r)
swap(l, r);
arr2.pb({l, -r});
}
sort(arr2.begin(), arr2.end());
for(int i = 0, mx = -1; i < n; i++){
int l = arr2[i].f;
int r = -arr2[i].s;
if(r <= mx)
continue;
mx = r;
arr.pb({l, r});
}
n = arr.size();
vector< ll > dp(n, INF);
vector< ll > last(n, INF);
ll ans = INF;
for(int q = 1; q <= k ; q++){
for(int i = 0; i < n; i++){
dp[i] = sqr(arr[i].s - arr[0].f + 1);
for(int j = 0; j < i; j++){
ll cur = last[j] + sqr(arr[i].s - arr[j + 1].f + 1) - sqr(max(0, arr[j].s - arr[j + 1].f + 1));
if(cur < dp[i])
dp[i] = cur;
}
}
if(ans > dp[n - 1])
ans = dp[n - 1];
for(int i = 0; i < n; i++)
last[i] = dp[i];
}
return ans;
}
