#include "aliens.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
int n, m, k;
ll dp[101010];
int cut[101010];
p a[101010];
vector<p> v;
struct CHT{
struct Line{
ll a, b, c;
Line(){ a = b = c = 0; }
Line(ll a, ll b, ll c) : a(a), b(b), c(c) {}
ll f(ll x){ return a*x+b; }
};
vector<Line> v; int pv;
void init(){ v.clear(); pv = 0; }
int chk(const Line &a, const Line &b, const Line &c){
return (a.b - b.b) * (c.a - b.a) >= (b.b - c.b) * (b.a - a.a);
}
void update(Line l){
if(v.size() && v.back().a == l.a){ v.back() = l; return; }
while(v.size() >= 2 && chk(v[v.size()-2], v.back(), l)) v.pop_back();
v.push_back(l);
if(pv >= v.size()) pv = v.size() - 1;
}
p query(ll x){
while(pv+1 < v.size() && v[pv].f(x) >= v[pv+1].f(x)) pv++;
return {v[pv].f(x), v[pv].c};
}
} cht;
void init(int N, int M, int K, const vector<int> &R, const vector<int> &C){
m = M, k = K; v.clear();
for(int i=0; i<N; i++) v.emplace_back(max(R[i], C[i]) + 1, min(R[i], C[i]));
sort(all(v));
for(int i=0; i<N; i++){
while(n && a[n].y >= v[i].y) n--;
a[++n] = v[i];
}
}
int chk(ll c){
cht.init(); cht.update(CHT::Line(-2 * a[1].y, a[1].y * a[1].y, 0));
for(int i=1; i<=n; i++){
auto t = cht.query(a[i].x);
dp[i] = t.x + a[i].x * a[i].x + c;
cut[i] = cut[t.y] + 1;
ll ta = a[i+1].y, tb = max(0LL, a[i].x - a[i+1].y);
ll aa = -2 * a[i+1].y;
ll bb = dp[i] + ta*ta - tb*tb;
cht.update(CHT::Line(aa, bb, i));
}
return cut[n];
}
ll take_photos(int N, int M, int K, vector<int> R, vector<int> C){
init(N, M, K, R, C);
int q = min(n, k);
ll l = 0, r = 1e15;
while(l < r){
ll m = l + r >> 1;
if(chk(m) <= q) r = m;
else l = m + 1;
}
chk(r);
return dp[n] - r * q;
}
// g++ -O2 -std=c++11 -static -o main grader.cpp aliens.cpp aliens.h
