#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<long long, long long>
vector<pii> points;
vector<pii> impt;
pii dp[100001];
deque<pair<pii, int>> dq;
long long f(pii line, long long x){
return line.first*x + line.second;
}
pii query(long long x){
while(dq.size()>1){ //to prevent seg fault when accessing dq[1]
long long fa = f(dq[0].first, x), fb = f(dq[1].first, x);
if (fa == fb){
if (dq[0].second > dq[1].second) dq.pop_front();
else break;
} else if(fa > fb) //the next line is better
dq.pop_front(); //remove useless line
else break;
}
return pii(f(dq[0].first,x), dq[0].second);
}
double intersect(long long m1, long long c1, long long m2, long long c2){
return (double)(c2-c1)/(m1-m2);
}
double intersect(pii p1, pii p2){
return intersect(p1.first,p1.second,p2.first,p2.second);
}
void insert(long long m,long long c, long long x) {//insert line y=mx+c
pii line = make_pair(m,c);
while (dq.size()>1) { //to prevent seg fault
int s = dq.size();
double a = intersect(dq[s-1].first, line), b = intersect(dq[s-2].first, line);
if (a <= b) dq.pop_back(); //removes useless line
else break;
}
dq.push_back({line, x});
}
long long sq(long long x){
return x*x;
}
pii check(long long c){
dq.clear();
dp[0] = {0, 0};
for (int i = 1; i < impt.size(); i++){
dp[i] = {sq(impt[i].second - impt[1].first + 1) + c, 1};
if (i != 1) {
insert(-2 * impt[i].first, sq(impt[i].first) - 2 * (impt[i].first) + dp[i-1].first - sq(max(0ll, impt[i-1].second - impt[i].first + 1)), dp[i-1].second);
pii g = query(impt[i].second);
g.first += sq(impt[i].second) + 2 * impt[i].second + c + 1;
g.second++;
dp[i] = min(dp[i], g);
}
/*
for (int j = 2; j <= i; j++){
dp[i] = min(dp[i], {dp[j-1].first + c + sq(impt[i].second - impt[j].first + 1) - sq(max(0ll, impt[j-1].second - impt[j].first + 1)), dp[j-1].second + 1});
}
*/
}
return dp[impt.size()-1];
}
// sq(impt[i].second - impt[j].first + 1)
// = dp[j-1].first + c + -2 * (impt[i].second) * (impt[j].first) + impt[i].second ^ 2 + 2 * impt[i].second + impt[j].first ^ 2 - 2 * (impt[j].first) + 1
// = [-2 * (impt[i].second) * (impt[j].first) + impt[j].first ^ 2 - 2 * (impt[j].first) + dp[j-1].first] + impt[i].second ^ 2 + 2 * impt[i].second + c + 1
long long take_photos(int N, int m, int K, std::vector<int> R, std::vector<int> C) {
for (int i = 0; i < N; i++) {
int r = R[i], c = C[i];
if (r > c) swap(r, c);
points.push_back({r, c});
}
impt.push_back({-1, -1}); // dummy
sort(points.begin(), points.end());
for (auto [a, b] : points){
if (impt.empty() || impt.back().second < b) impt.push_back({a, b});
}
//K = min(K, (int)impt.size()-1);
long long mini = -1, maxi = 1e16;
while (maxi - mini > 1){
long long mid = (maxi + mini) /2;
if (check(mid).second <= K) maxi = mid;
else mini = mid;
}
return check(maxi).first - K * maxi;
}
