#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int lint;
typedef __int128 llint;
typedef long double ldoub;
const int N = 1e5;
const llint PREC = 1e10;
array<llint, 2> ransDat[N];
vector<array<llint, 2>> rans;
llint dp[N+1];
int dp2[N+1];
int n, m;
void print(__int128 x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) print(x / 10);
putchar(x % 10 + '0');
}
llint slope(llint sl1p1, llint sl1p2, llint sl2p1, llint sl2p2){
for (int x = 0; x < 200; x ++){
llint k1 = sl1p1 / sl1p2;
llint k2 = sl2p1 / sl2p2;
if (k1 != k2){
return k1 - k2;
}
sl1p1 %= sl1p2;
sl2p1 %= sl2p2;
sl1p1 <<= 1;
sl2p1 <<= 1;
}
return 0;
}
void calc(llint adjust){
deque<array<llint, 3>> hull;
hull.push_back({rans[0][0], -rans[0][0] * rans[0][0], 0});
for (int x = 0; x < rans.size(); x ++){
llint s = -2 * rans[x][1];
llint B = rans[x][1] * rans[x][1];
int a = 1, b = hull.size()-1;
while (a <= b){
int mid = (b-a+1)/2 + a;
llint slp1 = (hull[mid][1] - hull[mid-1][1]);
llint slp2 = (hull[mid][0] - hull[mid-1][0]);
if (slope(slp1, slp2, s, (llint)1) < 0){
b = mid-1;
}else {
a = mid+1;
}
}
int r = a-1;
dp[x] = -hull[r][1] + B + hull[r][0] * s + adjust;
dp2[x] = hull[r][2] + 1;
/*
print(dp[x]);
cout << " ";
print((dp[x] - dp2[x]*adjust)/PREC/PREC);
cout << " " << dp2[x] << endl;
*/
if (x == rans.size()-1) continue;
llint right = min(rans[x][1], rans[x+1][0]);
array<llint, 3> p = {rans[x+1][0], -dp[x] + (rans[x][1] - right) * (rans[x][1] - right) - rans[x+1][0] * rans[x+1][0], dp2[x]};
while (hull.size() > 1){
llint sl1p1 = (p[1] - hull[hull.size()-2][1]);
llint sl1p2 = (p[0] - hull[hull.size()-2][0]);
llint sl2p1 = (hull[hull.size()-1][1] - hull[hull.size()-2][1]);
llint sl2p2 = (hull[hull.size()-1][0] - hull[hull.size()-2][0]);
if (slope(sl1p1, sl1p2, sl2p1, sl2p2) >= 0){
hull.pop_back();
}else {
break;
}
}
hull.push_back(p);
}
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
// dp_i = (pos_i-pos_j)**2 - (pos_right_j - pos_j)**2 + dp_j
// (pos_right_j - pos_j) ** 2 - dp_j - pos_j ** 2 = pos_i ** 2 - dp_i - 2 * pos_i * pos_j
// dp_i = (pos_i - pos_j + pos_right_j - pos_j) * (pos_i - pos_right_j) + dp_j
// dp_i = pos_i ** 2 - 2 * pos_j * pos_i + 2 * pos_j * pos_right_j - pos_right_j ** 2 + dp_j
// (pos_right_j ** 2 - 2 * pos_j * pos_right_j - dp_j) = pos_i ** 2 - dp_i + (- 2 * pos_j * pos_i)
//
// subsume all within range
// transition from possible left endpoints
::n = n;
::m = m;
for (int x = 0; x < n; x ++){
ransDat[x][0] = PREC*min(r[x], c[x]);
ransDat[x][1] = PREC*(max(r[x], c[x]) + 1);
}
sort(ransDat, ransDat+n, [](array<llint, 2> a, array<llint, 2> b){return (a[0] == b[0] ? a[1] > b[1] : a[0] < b[0]);});
{
llint ma = 0;
for (int x = 0; x < n; x ++){
if (ma >= ransDat[x][1]){
continue;
}
ma = ransDat[x][1];
rans.push_back(ransDat[x]);
}
}
k = min(k, (int)rans.size());
llint a = -(llint)1e12 * PREC * PREC, b = (llint)1e12 * PREC * PREC;
pair<llint, int> up = {1e12 * PREC*PREC, -1};
pair<llint, int> low = {1e12 * PREC*PREC, -1};
while (a <= b){
llint mid = (b-a+1)/2 + a;
llint v = mid;
calc(v);
/*
print(mid);
cout << " ";
print(dp[rans.size()-1]);
llint val = dp[rans.size()-1];
val -= dp2[rans.size()-1]*v;
val /= PREC;
val /= PREC;
cout << " ";
print(val);
cout << " " << dp2[rans.size()-1] << endl;;
*/
if (dp2[rans.size()-1] == k){
llint val = dp[rans.size()-1];
val -= k*v;
val /= PREC;
val /= PREC;
return (lint)val;
}
if (dp2[rans.size()-1] < k){
llint val = dp[rans.size()-1];
val -= dp2[rans.size()-1]*v;
val /= PREC;
val /= PREC;
up = min(up, {val, dp2[rans.size()-1]});
b = mid-1;
}else {
llint val = dp[rans.size()-1];
val -= dp2[rans.size()-1]*v;
val /= PREC;
val /= PREC;
low = min(low, {val, dp2[rans.size()-1]});
a = mid+1;
}
}
//llint best = ((up.first-low.first) * (k-low.second))/(up.second - low.second) + low.first;
//return best;
return up.first;
//return up.second * 1e12 + low.second*1e6 + k;
//exit(-1);
//return 0;
}
