#include "aliens.h"
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
vector<pair<int,int>> s;
vector<pair<int,int>> sorted;
int N;
int M;
vector<vector<int>> memo;
long long dp(int a, int left) {
if (memo[a][left] != -1) {
return memo[a][left];
}
int l = sorted[a].first;
int r = sorted[a].second;
long long out = -1;
for (int i = a; i < N; i++) {
r = max(r,sorted[i].second);
long long res = pow(r-l+1,2);
int j = i+1;
while (j < N && sorted[j].second <= r) {
j += 1;
}
if (j < N) {
if (left == 1) {
res = (1ll << 61);
}
res += dp(j,left-1);
res -= pow(max(0,r-sorted[j].first+1),2);
}
if (res < out || out == -1) {
out = res;
}
}
return memo[a][left] = out;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
N = n;
M = m;
s = vector<pair<int,int>>(n);
sorted = vector<pair<int,int>>(n);
memo = vector<vector<int>>(n,vector<int>(k+1,-1));
for (int i = 0; i < n; i++) {
if (r[i] > c[i]) {
int d = r[i]-c[i];
r[i] -= d;
c[i] += d;
}
}
for (int i = 0; i < n; i++) {
s[i] = make_pair(r[i],i);
}
sort(s.begin(),s.end());
for (int i = 0; i < n; i++) {
int index = s[i].second;
sorted[i] = make_pair(r[index],c[index]);
}
return dp(0,k);
}
