#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
const int MAX_N = 1e5 + 5;
const int MAX_M = 1e6 + 5;
const long long INF = 1e18 + 7;
int N, M, K;
long long X[MAX_N], Y[MAX_N];
int minL[MAX_M];
long long divide(long long a, long long b) {
return a / b - ((a ^ b) < 0 and a % b != 0);
}
struct Line {
long long m, c;
long long dot(long long x) {
return m * x + c;
}
long long intersect(const Line &o) {
return divide(o.c - c, m - o.m);
}
};
struct ConvexHullTrick {
deque <Line> dq;
void addLine(Line f) {
while (dq.size() >= 2 and dq.back().intersect(f) <= dq[dq.size() - 2].intersect(dq.back())) dq.pop_back();
dq.push_back(f);
}
long long query(long long x) {
while (dq.size() >= 2 and dq[0].dot(x) <= dq[1].dot(x)) dq.pop_front();
return dq[0].dot(x);
}
};
long long take_photos(int n, int m, int k, vector <int> r, vector <int> c) {
N = n, M = m, K = k;
for (int i = 0; i < m; i++) minL[i] = M;
for (int i = 0; i < N; i++) {
int x = min(r[i], c[i]), y = max(r[i], c[i]);
minL[y] = min(minL[y], x);
}
stack <pair <int, int>> stk;
for (int i = 0; i < m; i++) {
if (minL[i] == M) continue;
while (!stk.empty() and stk.top().first >= minL[i]) stk.pop();
stk.emplace(minL[i], i);
}
N = n = stk.size();
while (!stk.empty()) {
auto [x, y] = stk.top();
stk.pop();
X[n] = x, Y[n] = y;
n--;
}
X[N + 1] = Y[N + 1] = M;
vector <vector <long long>> dp(K + 1, vector <long long>(N + 1, INF));
dp[0][0] = 0;
for (int k = 1; k <= K; k++) {
ConvexHullTrick cht;
for (int i = 1; i <= N; i++) {
long long overlap = 1ll * max(0ll, Y[i] - X[i + 1] + 1) * max(0ll, Y[i] - X[i + 1] + 1);
cht.addLine({2 * X[i], -X[i] * X[i] - dp[k - 1][i - 1]});
dp[k][i] = -overlap + (Y[i] + 1) * (Y[i] + 1) - cht.query((Y[i] + 1));
}
}
long long ans = INF;
for (int k = 1; k <= K; k++) ans = min(ans, dp[k][N]);
return ans;
}
