#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N, M, K;
const ll INF = 1ll << 60ll;
ll take_photos(int N_, int M_, int K_, vector<int> X, vector<int> Y)
{
N = N_; M = M_; K = K_;
vector<int> dist(M), h(M);
for (int i = 0; i < N; i++)
{
if (X[i] > Y[i])
swap(X[i], Y[i]);
dist[X[i]] = max(dist[X[i]], Y[i] - X[i] + 1);
h[X[i]] = max(h[X[i]], Y[i] + 1);
}
int mx = 0;
vector<pair<ll, ll>> nodes;
for (int i = 0; i < M; i++)
{
if (h[i] <= mx)
{
dist[i] = h[i] = 0;
continue;
}
mx = h[i];
nodes.push_back({i, mx});
}
const int node_cnt = nodes.size();
nodes.push_back({M+1, M+1});
vector<vector<ll>> dp(node_cnt + 1, vector<ll>(K+1, INF));
for (auto&e : dp[0])
e = 0;
for (int k = 1; k <= K; k++)
{
int l = 0;
for (int i = 1; i <= node_cnt; i++)
{
ll sz = nodes[i-1].second - nodes[l].first;
ll overlap = max(0ll, nodes[l].first + sz - nodes[i].first);
ll area = dp[l][k-1] + sz * sz - overlap * overlap;
while (l + 1 != i)
{
ll n_sz = nodes[i-1].second - nodes[l+1].first;
ll n_overlap = max(0ll, nodes[l+1].first + n_sz - nodes[i].first);
ll n_area = dp[l+1][k-1] + n_sz*n_sz - n_overlap * n_overlap;
//cout << dp[l+1][k-1] << " + " << n_sz << "^2 - " << n_overlap << "^2 = " << n_area << '\n';
if (n_area > area) break;
l++;
sz = n_sz;
overlap = n_overlap;
area = n_area;
}
dp[i][k] = area;
}
}
return dp[node_cnt][K];
}
