#include "aliens.h"
#include <bits/stdc++.h>
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;
const long long NS = (long long)2e5 + 4;
long long n;
vector<long long> line[NS];
long long f, r;
long long cross(vector<long long> x, vector<long long> y){
long long val = (x[1] - y[1]) / (y[0] - x[0]);
return val + (val >= 0 && (x[1] - y[1]) % (y[0] - x[0]) ? 1 : 0);
}
void push(long long a, long long b, long long c){
while(f + 1 < r && cross({a, b}, line[r - 1]) <= cross(line[r - 1], line[r - 2])) --r;
line[r++] = {a, b, c};
}
pair<long long, long long> get(long long x){
while(f + 1 < r && line[f][0] * x + line[f][1] >= line[f + 1][0] * x + line[f + 1][1]) ++f;
return {line[f][0] * x + line[f][1], line[f][2]};
}
long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> C) {
vector<pair<long long, long long>> a(n);
for(long long i = 0; i < n; ++i){
a[i].first = R[i], a[i].second = C[i];
if(a[i].first > a[i].second){
swap(a[i].first, a[i].second);
}
}
sort(a.begin(), a.end());
vector<pair<long long, long long>> stk = {a[0]};
for(long long i = 1; i < n; ++i){
if(stk.back().first == a[i].first) ma(stk.back().second, a[i].second);
else if(stk.back().second < a[i].second) stk.push_back(a[i]);
}
a = stk; n = (long long)a.size();
long long low = (long long)-1e13, high = (long long)1e13;
auto sol = [&](long long pl)->pair<long long, long long>{
f = r = 0;
vector<pair<long long, long long>> dp(n);
push(-(a[0].first - 1) * 2 * 2, (a[0].first - 1) * (a[0].first - 1) * 2, 0);
for(long long i = 0; i < n; ++i){
auto rv = get(a[i].second);
dp[i] = {rv.first + a[i].second * a[i].second * 2 + pl, rv.second + 1};
auto nsame = 0;
if(i + 1 < n && a[i + 1].first <= a[i].second){
nsame = (a[i].second - a[i + 1].first + 1) * (a[i].second - a[i + 1].first + 1);
}
if(i + 1 < n) push(-(a[i + 1].first - 1) * 2 * 2, ((a[i + 1].first - 1) * (a[i + 1].first - 1) - nsame) * 2 + dp[i].first, dp[i].second);
}
return dp[n - 1];
};
mi(k, n);
while(low < high){
long long mid = low + high >> 1;
auto rv = sol(mid * 2 + 1);
//cout << low << ' ' << high << ' ' << mid << ' ' << rv.first << ' ' << rv.second << endl;
if(rv.second <= k){
high = mid;
}
else{
low = mid + 1;
}
}
low = low * 2;
auto rv = sol(low);
//cout << rv.first << ' ' << rv.second << ' ' << low << endl;
return ((rv.first - k * low) >> 1);
}
