#include "aliens.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return l + rd() % (r - l + 1);
}
const int N = 2e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
vector <pair <int, long long>> seg;
vector <long double> inter;
vector <int> ind;
pair <int, int> a[N];
long long dp[N];
int ptr[N];
int cnt[N];
int n,m,k,sz,cur;
typedef long long ll;
long double intersect(pair <int, ll> a, pair <int, ll> b) {
return (long double) (b.se - a.se) / (a.fi - b.fi);
}
bool good(pair <int, ll> a, pair <int, ll> b, pair <int, ll> c) {
long double xM = intersect(a, c);
long double xN = intersect(b, c);
return xM < xN;
}
void addLine(pair <int, ll> s, int i) {
while (sz > 1 && !good(seg[sz - 2], seg[sz - 1], s)) {
seg.pop_back();
inter.pop_back();
ind.pop_back();
sz--;
}
if (sz > 0)
inter.push_back(intersect(s, seg.back()));
seg.push_back(s);
ind.push_back(i);
sz++;
mini(cur, sz - 2);
}
int getopt(int x) {
while (cur + 1 < (int) inter.size() && x > inter[cur + 1])
cur++;
// cerr << x << " " << cur << "\n";
return cur;
}
int solve(long long cost) {
sz = 0;
inter.clear();
seg.clear();
ind.clear();
inter.push_back(-ooo);
a[n + 1] = mp(oo, oo);
for (int i = 1; i <= n; i++) {
long long add = 1LL * (a[i].se + 1) * (a[i].se + 1);
long long sub = 0;
if (a[i].se >= a[i + 1].fi) {
int d = a[i].se - a[i + 1].fi + 1;
sub = 1LL * d * d;
}
long long y = (dp[i - 1] + 1LL * a[i].fi * a[i].fi) + cost;
int x = -2 * a[i].fi;
addLine(mp(x, y), i - 1);
int it = -1;
// long long res = ooo;
// for (int j = 0; j < sz; j++)
// if (mini(res, 1LL * seg[j].fi * (a[i].se + 1)
// + seg[j].se - sub + add))
// it = j;
it = getopt(a[i].se + 1);
dp[i] = 1LL * seg[it].fi * (a[i].se + 1) + seg[it].se - sub + add;
cnt[i] = cnt[ind[it]] + 1;
ptr[i] = ind[it];
}
return cnt[n];
}
long long solve() {
long long lo = -1;
long long hi = 1e12 + 123;
while (hi - lo > 1) {
long long mid = (lo + hi) >> 1;
if (solve(mid) > k)
lo = mid;
else
hi = mid;
}
solve(hi);
return dp[n] - k * hi;
}
void build() {
for (int i = 1; i <= n; i++)
if (a[i].fi > a[i].se)
swap(a[i].fi, a[i].se);
sort(a + 1, a + n + 1, [](pair <int, int> a, pair <int, int> b) {
return (a.fi < b.fi) || (a.fi == b.fi && a.se > b.se);
});
int cur = -oo;
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (a[i].se > cur) {
cur = a[i].se;
a[++cnt] = a[i];
}
}
n = cnt;
}
long long 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++)
a[i] = mp(r[i - 1], c[i - 1]);
build();
return solve();
}
//#include "grader.cpp"
