#include "aliens.h"
#include <iostream>
#include <algorithm>
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define INF (1LL<<60)
#define all(x) (x).begin(), (x).end()
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> P;
struct CHT {
vector<pair<long long, long long> > ps;
void add(long long x, long long y) {
ps.pb(make_pair(x, y));
}
long long min(long long x) {
long long m = INF;
for (auto p : ps) m = std::min(m, p._1*x+p._2);
return m;
}
};
CHT dp[4001];
int L[100000], R[100000];
long long take_photos(int N, int M, int K, vector<int> RR, vector<int> CC) {
vector<P> ins;
rep(i, N) {
int l = min(RR[i], CC[i]), r = max(RR[i], CC[i]);
ins.pb(P(l, -r));
}
sort(all(ins));
vector<P> ins2;
int lp = -1;
for (P p : ins) {
int l = p._1, r = -p._2;
if (lp < r) {
ins2.pb(P(l, r));
lp = r;
}
}
swap(ins, ins2);
N = ins.size();
rep(i, N) L[i] = ins[i]._1, R[i] = ins[i]._2;
//rep(i, N) cout << "["<<ins[i]._1<<","<<ins[i]._2<<"]\n";
K = min(K, N);
dp[0].add(L[0], 1LL*L[0]*L[0]);
long long ans = INF;
rep(x, N) {
for (int k=K-1; k>=0; k--) {
long long m = dp[k].min(-2LL*(R[x]+1));
if (m == INF) continue;
m += 1LL*(R[x]+1)*(R[x]+1);
// cout<<"dp["<<x<<"]["<<k+1<<"]="<<m<<"\n";
if (x==N-1) {
ans = min(ans, m);
}
else {
long long overlap = 0;
if (L[x+1]<=R[x]) overlap = 1LL*(R[x]-L[x+1]+1)*(R[x]-L[x+1]+1);
dp[k+1].add(L[x+1], m+1LL*L[x+1]*L[x+1]-overlap);
}
}
}
return ans;
}
