#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<long long, long long> P;
double intersect(P s, P t) { return (double)(t._2-s._2)/(double)(s._1-t._1); }
struct CHT {
vector<P> ps;
int h = 0;
void add(long long x, long long y) {
auto c = P(x, y);
while (ps.size() >= 2) {
auto a = ps[ps.size()-2], b = ps[ps.size()-1];
if (intersect(b,c) < intersect(a,c) && intersect(a,c) < intersect(a,b)) break;
else ps.pop_back();
h = ::min(h, max(0, (int)ps.size()-1));
}
ps.pb(P(x, y));
}
long long min(long long x) {
if (ps.empty()) return INF;
while (h+1<ps.size() && intersect(ps[h+1], ps[h]) >= x) h++;
return ps[h]._1*x+ps[h]._2;
}
};
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;
}
