#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
const long long INF = 1e18;
struct line {
long long m, c;
line(long long _m = 0, long long _c = 0) {
m = _m, c = _c;
}
long long eval(long long x) {
return m * x + c;
}
long long isecX(line b) {
return ((long double) (b.c-c)) / (m - b.m);
}
};
struct CHT {
deque<line>dq;
int N = 0;
void insert(line l) {
while(N>=2 && l.isecX(dq[N-1]) < dq[N-1].isecX(dq[N-2])) dq.pop_back(), --N;
dq.push_back(l);
++N;
}
long long query(int x) {
while(N>=2 && dq[0].eval(x)>dq[1].eval(x)) dq.pop_front(), --N;
return dq[0].eval(x);
}
};
long long sq(long long x) {
return x * x;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
//fix the input
vector<pair<int,int>>ranges(n);
for(int i=0; i<n; ++i) {
ranges[i] = {min(r[i], c[i]), max(r[i], c[i])};
}
sort(ranges.begin(), ranges.end(), [&] (auto x, auto y) {
if(x.first==y.first) return x.second > y.second;
return x.first < y.first;
});
vector<pair<int,int>>new_ranges;
for(int i=0; i<n; ++i) {
if(!new_ranges.empty() && new_ranges.back().first<=ranges[i].first
&& new_ranges.back().second>=ranges[i].second);
else new_ranges.push_back(ranges[i]);
}
ranges = new_ranges;
n = ranges.size();
//do naive O(n*n*k) dp
// vector<long long>dp(n+10, INF);
// for(int j=k-1; j>=0; --j) {
// dp[n] = 0;
// vector<long long>new_dp(n+10, INF);
// for(int i=n-1; i>=0; --i) {
// for(int t=i+1; t<=n; ++t) {
// long long isec = (t<n) ? max(0, ranges[t-1].second-ranges[t].first+1) : 0;
// new_dp[i] = min(new_dp[i],
// dp[t] + sq(ranges[t-1].second - ranges[i].first + 1) - sq(isec));
// }
// }
// dp = new_dp;
// }
//optimize it with CHT
vector<long long>dp(n+10, INF);
for(int j=k-1; j>=0; --j) {
dp[n] = 0;
vector<long long>new_dp(n+10, INF);
CHT myCHT;
myCHT.insert(line(ranges[n-1].second, sq(ranges[n-1].second)));
for(int i=n-1; i>=0; --i) {
long long x = -2*(ranges[i].first-1);
long long y = myCHT.query(x);
new_dp[i] = y + sq(ranges[i].first-1);
if(i) {
long long isec = max(0, ranges[i-1].second-ranges[i].first+1);
myCHT.insert(line(ranges[i-1].second,
dp[i] + sq(ranges[i-1].second) - sq(isec)));
}
}
dp = new_dp;
}
//Aliens' Trick!
return dp[0];
}
