#include <bits/stdc++.h>
using namespace std;
struct node {
long long a, b;
int id;
node(long long a = 0, long long b = 1e18, int id = 0) : a(a), b(b), id(id) {
}
pair<long long, int> get(int x) {
return make_pair(a * x + b, id);
}
};
struct Eins {
vector<node> st;
vector<int> b;
int n;
Eins(vector<int>& b) : b(b) {
n = (int) b.size();
st.resize(n << 2 | 1);
}
void modify(int id, int l, int r, node val) {
int mid = l + r >> 1;
if (val.get(b[mid]) < st[id].get(b[mid])) swap(val, st[id]);
if (l == r) return ;
if (val.get(b[l]) < st[id].get(b[l])) modify(id << 1, l, mid, val);
if (val.get(b[r]) < st[id].get(b[r])) modify(id << 1|1, mid + 1, r, val);
}
pair<long long, int> get(int id, int l, int r, int x) {
auto ans = st[id].get(x);
if (l == r) return ans;
int mid = l + r >> 1;
if (x <= b[mid]) return min(get(id << 1, l, mid, x), ans);
return min(get(id << 1|1, mid + 1, r, x), ans);
}
};
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<pair<int,int>> a;
for (int i = 0; i < n; i++) {
if (r[i] < c[i]) swap(r[i], c[i]);
a.emplace_back(r[i], c[i]);
}
sort(a.begin(), a.end());
vector<pair<int,int>> b;
for (int i = 0; i < n; i++) {
while (!b.empty() && b.back().second >= a[i].second) b.pop_back();
b.push_back(a[i]);
}
swap(a, b);
n = (int) a.size();
auto test = [&](long long c) {
const long long inf = 1e18;
vector<pair<long long, int>> dp(n + 1, make_pair(inf, 0));
dp[0] = {0, 0};
vector<int> b;
for (int i = 0; i < n; i++) {
b.push_back(a[i].first);
}
sort(b.begin(), b.end());
b.resize(unique(b.begin(), b.end()) - b.begin());
Eins Tree(b);
/*
dp i = dp j + c + sq a[i-1].f - (a[j].s-1) = sq x - 2*x*(aj.s-1) + sq (aj.s-1)
*/
Tree.modify(1, 0, Tree.n - 1, node(-2 * (a[0].second - 1), c + 1ll * (a[0].second - 1) * (a[0].second - 1), 0));
for (int j = 1; j <= n; j++) {
/*for (int from = j; from > 0; from--) {
/*long long pre = (from > 1 ? a[from - 2].first : -1);
if (pre >= a[from - 1].second) pre = (pre - a[from - 1].second + 1) * (pre - a[from - 1].second + 1);
else pre = 0;
int pre = from > 1 ? a[from - 2].first : -1;
pre = max(0, pre - a[from - 1].second + 1);
dp[j] = min(dp[j], {dp[from - 1].first + 1ll * (a[j - 1].first - a[from - 1].second + 1) * (a[j - 1].first - a[from - 1].second + 1) + c - 1ll * pre * pre, dp[from - 1].second + 1});
}*/
auto x = Tree.get(1, 0, Tree.n - 1, a[j-1].first);
dp[j] = make_pair(x.first + 1ll * a[j-1].first * a[j-1].first, x.second + 1);
int pre = max(0, a[j-1].first - a[j].second + 1);
if (j < n) Tree.modify(1, 0, Tree.n - 1, node(-2 * (a[j].second - 1), dp[j].first + c + 1ll * (a[j].second - 1) * (a[j].second - 1) - 1ll * pre * pre, dp[j].second));
}
return dp[n];
};
long long l = 0, R = 1ll * m * m, ans = -1;
while (l <= R) {
long long mid = l + R >> 1;
if (test(mid).second <= k) {
ans = mid;
R = mid - 1;
}
else l = mid + 1;
}
assert(ans !=- 1);
return test(ans).first - ans * k;
}
/*
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout << take_photos(2, 7, 1, {2,3}, {3,4});
}*/
