#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 7;
const int K = 107;
const long long inf = 1e18;
bool cmp(pair<long long, long long> lvalue, pair<long long, long long> rvalue){
if(lvalue.first != rvalue.first){
return lvalue.first < rvalue.first;
}
return lvalue.second > rvalue.second;
}
pair<long long, long long> p[N];
long long dp[N][K];
long long calc_dp(int pos, int left){
if(pos < 0){
return 0;
}
return dp[pos][left];
}
void solve(int l, int r, int l2, int r2, int k){
if(l > r){
return;
}
int mid = (l + r) >> 1, ptr = -1;
dp[mid][k] = inf;
for(int i = min(mid, r2); i >= max(0, l2); i--){
long long curr = calc_dp(i - 1, k - 1);
curr += (p[mid].second - p[i].first + 1ll) * (p[mid].second - p[i].first + 1ll);
if(curr < dp[mid][k]){
dp[mid][k] = curr;
ptr = i;
}
}
if(p[mid].second >= p[mid + 1].first){
dp[mid][k] -= (p[mid].second - p[mid + 1].first + 1ll) * (p[mid].second - p[mid + 1].first + 1ll);
}
solve(l, mid - 1, l2, ptr, k);
solve(mid + 1, r, ptr, r2, k);
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
for(int i = 0; i < n; i++){
if(r[i] > c[i]){
swap(r[i], c[i]);
}
p[i].first = r[i];
p[i].second = c[i];
}
sort(p, p + n, cmp);
int mx = -1, j = 0;
for(int i = 0; i < n; i++){
if(p[i].second <= mx){
continue;
}
//cout << p[i].first << " p[i] " << p[i].second << endl;
mx = p[i].second;
p[j] = p[i];
j++;
}
n = j;
p[n].first = inf;
for(int i = 0; i < n; i++){
dp[i][0] = inf;
}
for(int i = 1; i <= k; i++){
solve(0, n - 1, 0, n - 1, i);
}
return dp[n - 1][k];
}
/*
5 7 2
0 3
4 4
4 6
4 5
4 6
*/
