#include "aliens.h"
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define pb push_back
#define mp make_pair
#define rept(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)
#define vec vector
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef vec<int> vi;
typedef vec<vi> v2i;
typedef pair<int, int> pi;
typedef vec<pi> vpi;
typedef vec<bool> vb;
typedef vec<ll> vl;
typedef vec<vl> v2l;
ll s1(int n, int m, vi& r, vi& c) {
ll ans = 0;
v2i g(m, vi(m, 0));
rep(i, n) {
if (r[i] > c[i]) swap(r[i], c[i]);
rept(y, r[i], c[i]+1) {
rept(x, r[i], c[i]+1) {
if (g[y][x] == 0) ans++;
g[y][x] = 1;
}
}
}
return ans;
}
ll s2(int n, int m, int k, vi& r) {
r.pb(-1);
sort(all(r));
v2l dp(r.size(), vl(k+1, 0));
rept(i, 1, n+1) {
rept(c, 1, k+1) {
dp[i][c] = dp[i-1][k-1] + 1;
rept(j, 1, i) {
dp[i][c] = min(dp[i][c], dp[i-j-1][k-1] + (r[i]-r[i-j]+1)*(r[i]-r[i-j]+1));
}
}
}
return dp[n][k];
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
if (n==k) return s1(n, m, r, c);
return s2(n, m, k, r);
}
