#include "aliens.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n';
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll Inf = 1e18;
const int N = 1e5 + 10;
const int K = N;
vector<ll> R, C;
int n, m, k;
pll dp[N];
ll Dup[N];
void Prep(){
ll r, c;
for(int i = 1; i < m; i++){
r = R[i]; c = C[i - 1];
if(c > r)
Dup[i] = (c - r) * (c - r);
}
//debug(Dup[1]);
}
/*
void SolveN2K(){
memset(dp, 31, sizeof dp);
dp[0][1] = (C[0] - R[0]) * (C[0] - R[0]);
for(int i = 1; i < m; i++){
for(int j = 1; j <= i + 1; j++){
for(int la = 1; la <= i; la ++){
dp[i][j] = min(dp[i][j], dp[la - 1][j - 1] - Dup[la] + (C[i] - R[la]) * (C[i] - R[la]));
}
}
dp[i][1] = min(dp[i][1], (C[i] - R[0]) * (C[i] - R[0]));
}
}
*/
//dp[i] = min(dp[i], {(dp[la - 1].F - Dup[la] + R[la] * R[la]) + (2*C[i] * (-R[la])) + (cost + C[i] * C[i]), dp[la - 1].S + 1});
typedef pair<ll, pair<pll, ll> > cht;
vector<cht> V;
ll Intersect(pll L1, pll L2, bool flg){
ll d = L2.S - L1.S;
ll M = L1.F - L2.F;
if(d % M == 0){
return d / M + (flg);
} else {
return d / M + (d >= 0);
}
}
void Add(pll Ln, ll cnt){
ll tmp;
while(!V.empty()){
tmp = Intersect(V.back().S.F, Ln, V.back().S.S <= cnt);
if(tmp <= V.back().F) V.pop_back();
else break;
}
tmp = -Inf;
if(!V.empty())
tmp = Intersect(V.back().S.F, Ln, V.back().S.S <= cnt);
V.pb({tmp, {Ln, cnt}});
}
pll Get(ll p){
assert(!V.empty());
auto it = upper_bound(all(V), cht(p, {{Inf, Inf}, Inf}));
it --;
return {it -> S.F.S + p * it->S.F.F,it -> S.S};
}
pll CheckN2(ll cost){
V.clear();
fill(dp, dp + N , pll(Inf, Inf));
dp[0] = {(C[0] - R[0]) * (C[0] - R[0]) + cost, 1};
//Add({-R[i], dp[i - 1].F - Dup[i] + R[i] * R[i]}, dp[i - 1].S);
for(int i = 1; i < m; i++){
Add({-R[i], dp[i - 1].F - Dup[i] + R[i] * R[i]}, dp[i - 1].S);
pll res = Get(2 * C[i]);
res.F += cost + C[i] * C[i];
res.S ++;
//for(int la = 1; la <= i; la ++){
// dp[i] = min(dp[i], {(dp[la - 1].F - Dup[la] + R[la] * R[la]) + (2*C[i] * (-R[la])) + (cost + C[i] * C[i]), dp[la - 1].S + 1});
//}
dp[i] = res;
dp[i] = min(dp[i], {(C[i] - R[0]) * (C[i] - R[0]) + cost, 1});
}
return dp[m - 1];
}
ll SolveN2LG(){
if(k == 1){
return (C[m - 1] - R[0]) * (C[m - 1] - R[0]);
}
if(k == m){
ll ans = 0;
for(int i = 0; i < m; i++){
ans += (C[i] - R[i]) * (C[i] - R[i]) - Dup[i];
}
return ans;
}
ll L = 0, R = 1e12, mid;
while(L + 1 < R){
mid = (L + R) >> 1;
if(CheckN2(mid).S <= k) R = mid;
else L = mid;
}
pll res = CheckN2(R);
//pll res2 = CheckN2(L);
//if(res2.S == k)
//return res2.F - res2.S * L;
ll ans = res.F - res.S * R;
ans -= R * (k - res.S);
return ans;
}
ll take_photos(int _m, int _n, int _k, vector<int> _r, vector<int> _c) {
n = _n; k = _k;
for(int i = 0; i < _m; i++)
if(_r[i] > _c[i])
swap(_r[i], _c[i]);
vector<int> I(_m);
iota(all(I), 0);
sort(all(I), [&](int i, int j){
return pii(_r[i], -_c[i]) < pii(_r[j], -_c[j]);
});
int mx = -1;
for(int i : I){
if(_c[i] > mx){
mx = _c[i];
R.pb(_r[i]);
C.pb(_c[i] + 1);
}
}
m = R.size();
ll ans = Inf;
//cerr << "! " << m << '\n';
//for(int i = 0; i < m; i++) cerr << R[i] << ' ' << C[i] << '\n';
Prep();
//SolveN2K();
k = min(k, m);
//for(int i = 1; i <= k; i++) ans = min(ans, dp[m - 1][i]);
ans = SolveN2LG();
return ans;
}
