//* Nigga we hit em up like motherfucking Tupac Shakur
#include "aliens.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const ll N = 1e6 + 10;
using ld = long double;
#define pb push_back
#define all(v) v.begin(), v.end()
ll n, m, k;
vector<pair<ll,ll> > v, x;
ll ans;
pair<ll,ll> dp[N];
ll L[N];
ll R[N];
ll cnt[N];
struct Line{
ll k, b;
ll id;
ll operator ()(ll x) {
return k * x + b;
}
};
vector<Line> st;
ld cross(Line x, Line y){
return (ld)(x.b - y.b) / (ld)(y.k - x.k);
}
void insert(Line nv){
ll m = st.size();
while(st.size() > 1 && cross(nv, st[m-1]) <= cross(st[m-1], st[m-2])){
st.pop_back();
--m;
}
st.pb(nv);
}
pair<ll,ll> query(ll x){
ll l = -1;
ll r = st.size() - 1;
while(r - l > 1){
ll mid = (l + r) / 2;
if(cross(st[mid], st[mid+1]) > x)r = mid;
else l = mid;
}
//++r;
return {st[r](x), st[r].id};
}
pair<ll,ll> f(ll C){
st.clear();
dp[0] = {0, 0};
for(ll i = 1;i<=n;i++){
insert({-L[i], dp[i-1].first + L[i] * L[i] - max(R[i-1] - L[i], 0ll) * max(0ll, R[i-1] - L[i]) + C, i -1});
pair<ll,ll> q = query(2 * R[i]);
dp[i].first = q.first + R[i] * R[i];
dp[i].second = dp[q.second].second + 1;
}
return dp[n];
}
long long take_photos(int nn, int mm, int kk, std::vector<int> rr, std::vector<int> cc) {
n = nn;
m = mm;
k = kk;
for(ll i = 1;i<=n;i++){
ll l = rr[i-1];
ll r = cc[i-1];
l++, r++;
if(l > r)swap(l, r);
v.pb({l, -r});
}
sort(all(v));
ll mx = 0;
x.pb({0, 0});
for(auto [l, r] : v){
r = -r;
if(r > mx){
mx = r;
x.pb({l, r});
}
}
sort(all(x));
n = x.size() - 1;
for(ll i = 1;i<=n;i++){
L[i] = x[i].first - 1;
R[i] = x[i].second;
}
ll l = -1;
ll r = 1e15;
ll ans = m * m;
k = min(n, k);
while(r - l > 1){
ll mid = (l + r) / 2;
if(f(mid).second > k){
l = mid;
}else{
r = mid;
}
}
//cout<<ans<<endl;
pair<ll,ll> p = f(l);
return p.first - k * l;
}
