#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pll pair<ll, ll>
#define pb push_back
using namespace std;
const int N = 1e5+5;
const int M = 2e5+5;
const ll mod = 1e9+7;
const int base = 400;
const ll inf = 1e16;
ll ans, tong, n, k, a[N], b[N], m, t, dp[N][2];
vector<pll> adj[N], kq;
string s;
pll p[N], f[N], res;
void cal(int l, int r, int opl, int opr, int j)
{
if(l > r)return;
int mid = (l+r)/2;
int best = mid;
dp[mid][j] = inf;
for(int i = opl; i <= min(mid, opr); i ++)
{
tong = dp[i-1][j^1] + (p[mid].se-p[i].fi+1)*(p[mid].se-p[i].fi+1);
if(i > 1)tong -= max(0ll, p[i-1].se-p[i].fi+1)*max(0ll, p[i-1].se-p[i].fi+1);
if(dp[mid][j] > tong)
{
dp[mid][j] = tong;
best = i;
}
}
cal(l, mid-1, opl, best, j);
cal(mid+1, r, best, opr, j);
}
struct line
{
ll a, b, id;
line(){};
line(ll _a, ll _b, ll _id)
{
a = _a;
b = _b;
id = _id;
}
ll f(ll x)
{
return a*x + b;
}
};
struct Hull
{
vector<line> q;
int pos = 0;
bool ccw(line x, line y, line z)
{
return x.a*(y.b-z.b) + y.a*(z.b-x.b) + z.a*(x.b-y.b) < 0;
}
void add(line d)
{
while(q.size() > 1 && !ccw(q[q.size()-2], q.back(), d))q.pop_back();
if(!q.empty())pos = min(pos, (int)q.size()-1);
else pos = 0;
q.pb(d);
}
pll get(ll x)
{
while(pos+1 <(int) q.size() && q[pos].f(x) > q[pos+1].f(x))++pos;
return {q[pos].f(x), q[pos].id};
}
};
bool cmp(pll& x, pll& y)
{
if(x.fi != y.fi)return x.fi < y.fi;
return x.se > y.se;
}
pll check(ll pen)
{
f[0] = {0, 0};
Hull hull;
for(int i = 1; i <= n; i ++)
{
tong = f[i-1].fi + p[i].fi*p[i].fi;
if(i > 1)tong -= max(0ll, p[i-1].se-p[i].fi+1)*max(0ll, p[i-1].se-p[i].fi+1);
hull.add(line(-2*p[i].fi, tong, f[i-1].se));
f[i] = hull.get(p[i].se+1);
f[i].fi += (p[i].se+1)*(p[i].se+1) + pen ;
f[i].se += 1;
}
return f[n];
}
ll take_photos(int N, int M, int K, vector<int> r, vector<int> c)
{
n = N;
m = M;
k = K;
for(int i = 1; i <= n; i ++)
{
p[i].fi = r[i-1];
p[i].se = c[i-1];
if(p[i].fi > p[i].se)swap(p[i].fi, p[i].se);
}
sort(p+1, p+1+n, cmp);
for(int i = 1; i <= n; i ++)
{
if(!kq.empty() && kq.back().se >= p[i].se)continue;
kq.pb(p[i]);
}
n = kq.size();
for(int i = 1; i <= n; i ++)p[i] = kq[i-1];
ll lf = 0, rt = m*m, mid;
while(lf <= rt)
{
mid = (lf+rt)/2;
if(check(mid).se > k)lf = mid+1;
else rt = mid-1;
}
res = check(lf);
//cout << rt <<" "<<res.fi<<" "<<res.se <<" "<<k<<'\n';
return res.fi - k*lf;
}
