#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, long long> ii;
vector<ii> allRanges; ///all the ranges
vector<ii> arr; ///non-overalping ranges we need to consider
inline long long square(long long x){ return x * x; }
bool comp(ii a, ii b){
if(a.first == b.first) return a.second > b.second;
return a.first < b.first;
}
struct Line{ long long m, c, taken; };
inline long double intersect(Line a, Line b){
return (long double) (b.c - a.c) / (long double) (a.m - b.m);
}
struct ConvexHull{
Line hull[100005];
int l = 0, r = -1;
void reset(){
l = 0, r = -1;
}
///take as many if tie by cost
bool redundantBack(){
if(r - l < 2) return false;
if(abs(intersect(hull[r],hull[r-1]) - intersect(hull[r-2],hull[r])) <= 0.00000001) return hull[r].taken > hull[r-1].taken;
return intersect(hull[r-1],hull[r-2]) > intersect(hull[r],hull[r-2]);
}
///return the best value, and also how many ranges taken
ii getBest(long long k){
while(r - l > 0 && intersect(hull[l],hull[l+1]) < (long double) k) l++;
long long ans = (hull[l].m * k + hull[l].c);
return ii(ans, hull[l].taken);
}
void addLine(long long m, long long c, long long taken){
if(r - l < 0 || hull[r].m > m) hull[++r] = {m,c,taken};
else if(hull[r].c > c) hull[r] = {m,c,taken};
else if(hull[r].c == c && hull[r].taken < taken) hull[r] = {m,c,taken}; ///tiebreak by no. taken
while(redundantBack()){
hull[r-1] = hull[r];
r--;
}
}
} ch;
///This is the dp part. There is no restriction on the number of ranges.
///However, the dp value increases by cost for every range taken.
///This returns the optimum value and the max no. of ranges taken for that value of cost
inline ii monge(long long cost){
ch.reset();
ch.addLine(-2LL * arr[0].first, square(arr[0].first), 1); ///option for taking from the start
ii dp; ///ii(bestAns, taken)
for(int i = 0;i < (int) arr.size();i++){
ii x = arr[i];
dp = ch.getBest(x.second);
dp.first += square(x.second);
dp.first += cost; ///add a cost for taking a range
if(i != (int) arr.size() - 1){
long long gradient = -2 * arr[i+1].first;
long long yIntercept = dp.first - square(max(0LL, arr[i].second - arr[i+1].first)) + square(arr[i+1].first);
ch.addLine(gradient, yIntercept, dp.second + 1);
}
}
return dp;
}
long long take_photos(int n, int m, int K, vector<int> L, vector<int> R) {
for(int i = 0;i < n;i++){
if(L[i] > R[i]) swap(L[i], R[i]);
allRanges.push_back(ii(L[i],R[i]));
}
///sort the ranges
sort(allRanges.begin(),allRanges.end(),comp);
///remove all ranges which are fully contained in another
int maxR = -1;
for(ii r : allRanges){
if(r.second > maxR){
maxR = r.second;
arr.push_back(ii(r.first,r.second+1));
}
}
if(arr.size() == 1){
return square(arr[0].second - arr[0].first);
}
long long low = -1;
long long high = square(m);
///Let f(k) be the answer to the problem where k is the no. of ranges we take
///f is concave upwards [f(i) - f(i+1) <= f(i-1) - f(i)], diminishing returns
///Hence, if we let g(k) = f(k) + k * cost, then g(k) has a local minimum where gradient of f(k) = C
///As C increases, the local minimum point decreases (greater cost -> take fewer ranges)
///We can binary search the value of C such that the local minimum point occurs at K given in the qn
while(true){
if(low == high - 1) break;
long long s = (low + high) / 2LL;
if(monge(s).second <= K) high = s;
else low = s;
}
///We need to do linear interpolation since the function is not strictly concave up
ii ansHigh = monge(high);
long long ans = ansHigh.first - K * high;
return ans;
}
