#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define pb push_back
#define all(v) (v).begin(), (v).end()
typedef long long lld;
int N, M, K;
lld D[MAXN], E[MAXN];
int stk[MAXN]; double xpos[MAXN]; int scnt;
struct Z{
int r, c;
} A[MAXN];
lld y_intercept(int n)
{
lld ret = E[n] + (lld)A[n+1].r*A[n+1].r - 2*A[n+1].r;
if (A[n+1].r <= A[n].c) ret -= (lld)(A[n].c-A[n+1].r+1)*(A[n].c-A[n+1].r+1);
return ret;
}
double get_cross(int a, int b)
{
// slope: -2A[i+1].r
return (y_intercept(b) - y_intercept(a)) / (-2.) / (A[a+1].r - A[b+1].r);
}
lld take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
M = m, K = k;
vector <Z> arr;
for (int i=0;i<n;i++) arr.pb({min(r[i], c[i]), max(r[i], c[i])});
sort(all(arr), [](const Z &a, const Z &b){
return a.c != b.c ? a.c < b.c : a.r > b.r;
});
for (Z &z: arr){
while (N && A[N].r >= z.r) N--;
A[++N] = z;
}
K = min(K, N);
for (int i=1;i<=N;i++) D[i] = (lld)(A[i].c-A[1].r+1)*(A[i].c-A[1].r+1);
for (int k=2;k<=K;k++){
for (int i=1;i<=N;i++) E[i] = D[i];
int pt = 1;
scnt = 0;
for (int i=k;i<=N;i++){
while (scnt && get_cross(stk[scnt], i-1) < xpos[scnt]) scnt--;
if (pt > scnt) pt = scnt;
stk[++scnt] = i-1;
if (scnt == 1) xpos[scnt] = -1e18;
else xpos[scnt] = get_cross(stk[scnt-1], stk[scnt]);
while (pt < scnt && xpos[pt+1] < A[i].c) pt++;
int j = stk[pt];
D[i] = y_intercept(j) - 2LL*A[j+1].r*A[i].c + (lld)A[i].c*A[i].c + 2*A[i].c + 1;
}
}
return D[N];
}
