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

using namespace std;

namespace {

typedef long long ll;

const int N = 1e5 + 7;
const ll INF = 4e18;

struct convhull {
	struct line {
		ll k, b;
	};

	vector<line> st;

	bool bad(line l1, line l2, line l3) {
		return (l3.b - l1.b) * (l2.k - l1.k) <= (l2.b - l1.b) * (l1.k - l3.k);
	}

	void add(ll k, ll b) {
		line l = {k, b};
		if (!st.empty()) {
			assert(k < st.back().k);
		}
		while (st.size() >= 2 && bad(st[st.size() - 2], st.back(), l)) {
			st.pop_back();
		}
		st.push_back(l);
	}

	bool good(line l1, line l2, ll x) {
		return l2.b - l1.b <= x * (l1.k - l2.k);
	}

	ll get(ll x) {
		if (st.empty()) {
			return INF;
		}
		ll ret = INF;
		for (auto l : st) {
			ret = min(ret, l.k * x + l.b);
		}
		return ret;
		// int l = 0, r = st.size();
		// while (r - l > 1) {
		// 	int m = (l + r) / 2;
		// 	if (good(st[m - 1], st[m], x)) {
		// 		l = m;
		// 	} else {
		// 		r = m;
		// 	}
		// }
		// return st[l].k * x + st[l].b;
	}
};


int n, k;
ll l[N], r[N];
ll pref[N];
ll kek[N];
pair<ll, int> dp[N];
convhull ch[N];

void add(int i) {
	ll k = -l[i];
	ll b = dp[i].first + pref[i] - kek[i] + l[i] * l[i];
	ch[dp[i].second].add(k, b);
}

pair<ll, int> solve(ll cost) {
	for (int i = 1; i <= n; ++i) {
		dp[i] = {INF, n + 1};
	}
	for (int i = 0; i <= n; ++i) {
		ch[i].st.clear();
	}
	dp[0] = {0, 0};
	add(0);
	for (int j = 1; j <= n; ++j) {
		for (int t = dp[j - 1].second; t >= 0/*max(0, dp[j - 1].second - 1)*/; --t) {
			pair<ll, int> ndp;
			ndp.first = ch[t].get(2 * r[j - 1]) + r[j - 1] * r[j - 1] - pref[j] + cost;
			ndp.second = t + 1;
			dp[j] = min(dp[j], ndp);
		}
		if (j < n) {
			add(j);
		}
	}
	return dp[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 (n == 0 || r1 > r[n - 1]) {
			l[n] = l1;
			r[n] = r1;
			++n;
		}
	}
	kek[0] = 0;
	for (int i = 1; i < n; ++i) {
		kek[i] = r[i - 1] >= l[i] ? (r[i - 1] - l[i]) * (r[i - 1] - l[i]) : 0;
	}
	pref[0] = 0;
	for (int i = 0; i < n; ++i) {
		pref[i + 1] = pref[i] + (r[i] - l[i]) * (r[i] - l[i]) - kek[i];
	}
	k = min(k, n);
	ll l = 0, r = 1e12;
	while (r - l > 1) {
		ll m = (l + r) / 2;
		if (solve(m).second <= k) {
			r = m;
		} else {
			l = m;
		}
	}
	ll ans = solve(r).first - k * r;
	ans += pref[n];
	return ans;
}