#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
const long long INF = 1e18;
long long sq(long long x) {
return x * x;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
//fix the input
vector<pair<int,int>>ranges(n);
for(int i=0; i<n; ++i) {
ranges[i] = {min(r[i], c[i]), max(r[i], c[i])};
}
sort(ranges.begin(), ranges.end(), [&] (auto x, auto y) {
if(x.first==y.first) return x.second > y.second;
return x.first < y.first;
});
vector<pair<int,int>>new_ranges;
for(int i=0; i<n; ++i) {
if(!new_ranges.empty() && new_ranges.back().first<=ranges[i].first
&& new_ranges.back().second>=ranges[i].second);
else new_ranges.push_back(ranges[i]);
}
ranges = new_ranges;
n = ranges.size();
//do naive O(n*n*k) dp
vector<long long>dp(n+10, INF);
for(int j=k-1; j>=0; --j) {
dp[n] = 0;
vector<long long>new_dp(n+10, INF);
for(int i=n-1; i>=0; --i) {
for(int t=i+1; t<=n; ++t) {
long long isec = (t<n) ? max(0, ranges[t-1].second-ranges[t].first+1) : 0;
new_dp[i] = min(new_dp[i],
dp[t] + sq(ranges[t-1].second - ranges[i].first + 1) - sq(isec));
}
}
dp = new_dp;
}
return dp[0];
//optimize it with CHT
//Aliens' Trick!
}
