#include<bits/stdc++.h>
#include "aliens.h"
using namespace std;
typedef long long ll;
#define pi pair <int, int>
#define sz(x) (int)((x).size())
const int N = 100010 + 11;
const ll INF64 = 2e18;
struct interval{
long long l,r;
};
interval a[N];
long long dp[N], cnt[N], n, m, k;
struct line{
long long a,b, cnt;
long long val(int x){
return a*x + b;
}
};
double cross(line a, line b){
return (a.b - b.b)/(b.a - a.a);
}
bool cmp(interval x, interval y){
if(x.l != y.l)return (x.l < y.l);
return (x.r > y.r);
}
long long P(long long x){
return x * x;
}
void solve(long long lambda){
deque<line>dq;
for(int i = 1; i <= n; i++){
line cur = {-2*a[i].l, P(a[i].l) + dp[i - 1] - P(max(0ll, a[i - 1].r - a[i].l + 1ll)), cnt[i - 1] + 1ll};
while(sz(dq) >= 2 && cross(cur,dq[sz(dq) - 1]) < cross(dq[sz(dq) - 1],dq[sz(dq) - 2]))dq.pop_back();
dq.push_back(cur);
while(sz(dq) >= 2 && cross(dq[0],dq[1]) < (a[i].r + 1))dq.pop_front();
cnt[i] = dq.front().cnt;
dp[i] = dq.front().val(a[i].r + 1) + P(a[i].r + 1) + lambda;
}
}
long long take_photos (int N, int M, int K, std::vector <int> r, std::vector <int> c){
n = N, m = M, k = K;
for(int i = 0; i < n; i++){
a[i + 1].l = min(r[i], c[i]);
a[i + 1].r = max(r[i], c[i]);
}
sort(a + 1, a + n + 1, cmp);
a[0].l = a[0].r = -1;
long long L = -1, R = -1, cur = 0;
for(int i = 1; i <= n; i++){
if(!(L <= a[i].l && a[i].r <= R)){
a[++cur] = a[i];
L = a[i].l;
R = a[i].r;
}
}
n = cur;
k = min(k, n);
long long st = 0ll, dr = INF64;
while(st <= dr){
long long mid = (st + dr) >> 1;
solve(mid);
if(cnt[n] > k)st = mid + 1;else dr = mid - 1;
}
solve(st);
return dp[n] - st*k;
}
