#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

namespace {

typedef long long ll;

const int N = 505;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, k;
int l[N], r[N];
ll dp[N][N];
ll pref[N];

}

ll take_photos(int grdn, int grdm, int grdk, vector<int> grdr, vector<int> grdc) {
	k = grdk;
	vector<pair<int, int>> segs;
	for (int i = 0; i < grdn; ++i) {
		int r = grdr[i];
		int c = grdc[i];
		if (r <= c) {
			segs.push_back({r, c + 1});
		} else {
			segs.push_back({c, r + 1});
		}
	}
	sort(segs.begin(), segs.end());
	n = 0;
	for (auto sg : segs) {
		int l1 = sg.first;
		int r1 = sg.second;
		if (n > 0 && l1 == l[n - 1] && r1 > r[n - 1]) {
			--n;
		}
		if (r1 > r[n - 1]) {
			while (n > 1 && r[n - 2] >= l1) {
				--n;
			}
			l[n] = l1;
			r[n] = r1;
			++n;
		}
	}
	pref[0] = 0;
	for (int i = 0; i < n; ++i) {
		pref[i + 1] = pref[i] + (r[i] - l[i]) * 1ll * (r[i] - l[i]);
	}
	memset(dp, 0x3f, sizeof dp);
	for (int i = 0; i < n; ++i) {
		dp[1][i + 1] = (r[i] - l[0]) * 1ll * (r[i] - l[0]) - pref[i + 1];
	}
	for (int t = 1; t < k; ++t) {
		for (int i = 1; i <= n; ++i) {
			dp[t + 1][i] = min(dp[t + 1][i], dp[t][i]);
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = i + 1; j <= n; ++j) {
				dp[t + 1][j] = min(dp[t + 1][j], dp[t][i] + (r[j - 1] - l[i]) * 1ll * (r[j - 1] - l[i]) - pref[j] + pref[i]);
			}
		}
	}
	ll ans = dp[k][n];
	ans += pref[n];
	for (int i = 0; i < n - 1; ++i) {
		if (r[i] >= l[i + 1]) {
			ans -= (r[i] - l[i + 1]) * 1ll * (r[i] - l[i + 1]);
		}
	}
	for (int i = 0; i < n - 2; ++i) {
		assert(r[i] < l[i + 2]);
	}
	return ans;
}