#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
char _;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template <typename t> void scan (t& x) {do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0);}
template <typename t, typename ...r> void scan (t& x, r&... xs) {scan(x); scan(xs...);}
const int MN = 4e3+2;
vector<pii> points;
vector<pii> fin;
ll dp[MN][MN];
ll o[MN];
pll lines[MN];
ll area (int j, int i) {
int x = fin[i].second - fin[j].first + 1;
return (ll)x*x;
}
void overlap (int j) {
int x = max(0,fin[j-1].second - fin[j].first + 1);
o[j] = (ll)x*x;
}
ll f (int j, int i) {
return 0;
}
ll take_photos (int n, int m, int K, vector<int> r, vector<int> c) {
for (int i = 0; i < n; i++) points.emplace_back(min(r[i],c[i]),max(r[i],c[i]));
sort(all(points),[](pii a, pii b) {return a.first == b.first ? a.second > b.second : a.first < b.first;});
for (int i = 0; i < n; i++) {
if (!fin.empty() && fin.back().first <= points[i].first && fin.back().second >= points[i].second) continue;
fin.push_back(points[i]);
}
//area of smallest photo covering point j & point i (j < i) = (points[i].second - points[j].first + 1)^2
//area of overlap for left point j is max(0,points[j-1].second - points[j].first + 1)^2
//f[i][j] = area of photo - area of overlap
n = fin.size();
for (int i = 1; i <= n; i++) dp[1][i] = area(0,i-1);
o[0] = 0;
for (int i = 1; i < n; i++) overlap(i);
for (int k = 2; k <= K; k++) {
for (int i = 1; i <= n; i++) {
dp[k][i] = LLONG_MAX>>1;
for (int j = i; j >= 1; j--) {
dp[k][i] = min(dp[k][i],dp[k-1][j-1] + fin[i-1].second * 1LL * fin[i-1].second + fin[j-1].first * 1LL * fin[j-1].first + 1LL - 2LL * fin[i-1].second * fin[j-1].first - 2LL * fin[j-1].first + 2LL * fin[i-1].second - o[j-1]);
}
}
}
return dp[K][n];
}
