#include "aliens.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;
#define cerr if(1) cerr
const Int INF = 1e16;
// Max convex hull trick
// To get minimum cht
// Transform m and c to -m and -c before calling _upd()
// Transform _qry() to -_qry()
struct Line {
mutable Int m, c, p;
bool operator<(const Line& o)const{ return m<o.m;}
bool operator<(Int x)const{return p<x;}
};
struct Cht:multiset<Line, less<>> {
static const bool MINCHT = 1;
// (for doubles, use INF = 1/.0, div(a,b) = a/b)
inline Int div(Int a,Int b){ // floored division
return a/b - ((a^b)<0 && a%b);
}
bool isect(iterator x,iterator y){ // check Intersection
if(y==end()) return x->p = INF, 0;
if(x->m==y->m) x->p = x->c > y->c ? INF : -INF;
else x->p = div(y->c - x->c, x->m - y->m);
return x->p >= y->p;
}
void _upd(Int m,Int c){ // insert line m*x+c
auto z = insert({m,c,0}), y=z++, x=y;
while(isect(y,z)) z = erase(z);
if(x!=begin() && isect(--x,y)) isect(x, y=erase(y));
while((y=x)!=begin() && (--x)->p>=y->p) isect(x, erase(y));
}
void upd(Int m,Int c){
MINCHT ? _upd(-m,-c) : _upd(m,c);
}
Int _qry(Int x){ // find maximum m*x+c
if(empty()) return -INF;
auto l = *lower_bound(x);
return l.m*x+l.c;
}
Int qry(Int x){
return MINCHT ? -_qry(x) : _qry(x);
}
} cht;
const int N = 5e4+5;
const int K = 505;
const int M = 1e6+5;
int n, m, k;
Int dp[N][2];
inline Int sqr(Int x){return x*x;}
Int take_photos(int _n,int _m,int _k,V<int> _l,V<int> _r){
n = _n; m = _m; k = _k;
V<Int> l(all(_l)), r(all(_r));
// remove subsegments
V<int> ord;
rep(i,0,n){
if(l[i] > r[i]) swap(l[i], r[i]);
ord.push_back(i);
}
sort(all(ord),[&](int i,int j){
if(l[i]==l[j]) return r[i] < r[j];
return l[i] > l[j];
});
V<int> stak;
for(int i : ord){
while(!stak.empty() && r[stak.back()]<=r[i]) stak.pop_back();
stak.push_back(i);
}
reverse(all(stak));
ord.swap(stak);
// result is ordered from l
// reorder l[] and r[]
{
V<Int> vl, vr;
for(int i : ord){
// cerr << l[i] _ r[i] << nl;
vl.push_back(l[i]);
vr.push_back(r[i]);
}
l.swap(vl);
r.swap(vr);
}
n = ord.size();
// // dp[0][p]
// rep(p,1,k+1) dp[0][p] = sqr(r[0]-l[0]+1);
// dp[i][0]
rep(i,0,n) dp[i][0] = INF;
rep(pp,1,k+1){
int p = pp&1;
// dbg(p);
dp[0][p] = sqr(r[0]-l[0]+1);
rep(i,1,n){
// dp[i][p] = sqr(r[i]-l[0]+1);
// rep(j,1,i+1) dp[i][p] = min(dp[i][p],
// dp[j-1][p^1] +sqr(r[i]-l[j]+1) -(l[j]<=r[j-1] ? sqr(r[j-1]-l[j]+1):0)
// );
if(l[i] <= r[i-1]){
cht.upd(-2*l[i], l[i]*l[i]-2*l[i] +dp[i-1][p^1] -sqr(r[i-1]-l[i]+1));
}
else{
cht.upd(-2*l[i], l[i]*l[i]-2*l[i] +dp[i-1][p^1]);
}
dp[i][p] = r[i]*r[i] +2*r[i] +1 +cht.qry(r[i]);
dp[i][p] = min(dp[i][p], sqr(r[i]-l[0]+1));
// dbg(dp[i][p]);
}
}
Int ans = dp[n-1][k&1];
return ans;
}
