#include <bits/stdc++.h>
#include<aliens.h>
using namespace std;
const int N = 1e6 + 3, MOD = 1e9 + 7;
typedef long long ll;
int n,m,k;
vector<pair<ll,ll>> a,x;
ll res;
ll dp[N],L[N],R[N];
int col[N];
struct line{
ll k,b;
int id;
ll calc(ll x){
return k * x + b;
}
};
vector<line> st;
long double cross(line x,line y){
return (long double)(x.b - y.b) / (long double)(y.k - x.k);
}
void add(line nv){
int m = (int)st.size();
while(st.size() > 1 && cross(nv,st[m - 1]) <= cross(st[m - 1],st[m - 2])){
st.pop_back();
m--;
}
st.push_back(nv);
}
pair<int,ll> get(ll x){
int l = -1,r = (int)st.size() - 1;
while(r - l > 1){
int mid = (l + r) >> 1;
if(cross(st[mid],st[mid + 1]) > (long double)x){
r = mid;
}else{
l = mid;
}
}
ll mn = 1e18;
int ret = 1e9;
for(auto j:st){
if(j.calc(x) <= mn){
mn = j.calc(x);
ret = j.id;
}
}
// if(st[r].id != ret) {
// cout << st[r].id << ' ' << ret << "x\n";
// cout << x << '\n';
// for(int i = 0;i < (int)st.size() - 1;i++){
// cout << cross(st[i],st[i + 1]) << ' ';
// }
// cout << '\n';
// for(auto j:st){
// cout << j.id << ' ';
// }
// cout << '\n';
//
// exit(0);
// }
return {st[r].id,st[r].calc(x)};
}
ll f(ll pen){
st.clear();
dp[0] = 0;
col[0] = 0;
for(int i = 1;i <= n;i++){
add({-L[i], dp[i - 1] + L[i] * L[i] - max(R[i - 1] - L[i], 0ll) * max(0ll, R[i - 1] - L[i]) + pen,i});
pair<int,ll> g = get(2 * R[i]);
dp[i] = g.second + R[i] * R[i];
col[i] = col[g.first - 1] + 1;
}
res = dp[n];
return col[n];
}
long long take_photos(int nn,int mm,int kk,vector<int> rr,vector<int> cc){
n = nn;
m = mm;
k = kk;
for(int i = 1;i <= n;i++){
int l = rr[i - 1],r = cc[i - 1];
++l;++r;
if(l > r){
swap(l,r);
}
a.push_back({l,-r});
}
sort(a.begin(),a.end());
int mx = 0;
x.push_back({0,0});
for(auto [l,r]:a){
r = -r;
if(r > mx){
mx = r;
x.push_back({l,r});
}
}
sort(x.begin(),x.end());
n = (int)x.size() - 1;
for (int i = 1; i <= n; i++) {
L[i] = x[i].first - 1;
R[i] = x[i].second;
}
ll l = -1,r = 1e15;
k = min(k,n);
while(r - l > 1) {
ll mid = (l + r) >> 1;
if (f(mid) >= k) {
l = mid;
} else {
r = mid;
}
}
ll x = f(l);
return res - k * 1ll * l;
}
