#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 = 1e9;
array<llint, 2> rans[N];
llint dp[N+1];
int dp2[N+1];
int n, m;
int term;
void calc(llint c){
dp[0] = 0;
dp2[0] = 0;
deque<array<llint, 3>> hull;
hull.push_back({0, 0, 0});
array<llint, 2> ma = {0, 0};
term = 0;
for (int x = 1; x <= n; x ++){
if (ma[0] >= rans[x-1][1]){
continue;
}
llint s = -2 * rans[x-1][1];
llint B = rans[x-1][1] * rans[x-1][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 (slp1 < s * slp2){
b = mid-1;
}else {
a = mid+1;
}
}
int r = a-1;
//cout << r << endl;
// (pos_right_j ** 2 - 2 * pos_j * pos_right_j - dp_j) = pos_i ** 2 - dp_i + (- 2 * pos_right_j * pos_i)
// hull[r][1] = B - dp_i + s * hull[0]
// dp_i = B - hull[r][1] + s * hull[0]
dp[x] = -hull[r][1] + B + hull[r][0] * s + c;
dp2[x] = dp2[(int)hull[r][2]] + 1;
{
llint l = max(ma[0], rans[x-1][0]);
llint r = (rans[x-1][1] - rans[x-1][0]) * (rans[x-1][1] - rans[x-1][0]) - (l - rans[x-1][0]) * (l - rans[x-1][0]) + dp[ma[1]] + c;
if (r < dp[x]){
dp[x] = r;
dp2[x] = dp2[ma[1]] + 1;
}
}
//cout << (lint)dp[x] << " " << dp2[x] << endl;
llint right = max(rans[x-1][0], ma[0]);
array<llint, 3> p = {right, right * right - 2 * rans[x-1][0] * right - dp[ma[1]], ma[1]};
if (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 (sl1p1*sl2p2 >= sl2p1*sl1p2){
hull.pop_back();
}
}
hull.push_back(p);
ma = {rans[x-1][1], x};
term = x;
}
}
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
// 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_right_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_right_j * pos_i)
//
// subsume all within range
// transition from possible left endpoints
::n = n;
::m = m;
for (int x = 0; x < n; x ++){
rans[x][0] = PREC*min(r[x], c[x]);
rans[x][1] = PREC*(max(r[x], c[x]) + 1);
}
sort(rans, rans+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;
int tot = 0;
for (int x = 0; x < n; x ++){
if (rans[x][1] > ma){
tot ++;
}
ma = rans[x-1][1];
}
k = min(tot, k);
}
llint a = -1e12 * PREC, b = 1e12 * PREC;
while (a <= b){
llint mid = (b-a+1)/2 + a;
llint v = mid;
calc(v);
//cout << (lint)mid << " " << dp2[term] << " " << (lint)dp[term] << endl;
if (dp2[term] == k){
llint val = dp[term];
val -= k*v;
val /= PREC;
val /= PREC;
return (lint)val;
}
if (dp2[term] < k){
b = mid-1;
}else {
a = mid+1;
}
}
throw runtime_error("DID NOT FIND ANSWER\n");
//exit(-1);
//return 0;
}
