#include <bits/stdc++.h>
#ifndef LOCAL
#include "aliens.h"
#endif // LOCAL
using namespace std;
using ll = long long;
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v)
#define dbg(x) "[" #x " = " << (x) << "]"
#define sz(v) (int)v.size()
template<typename T> bool minimize(T& a, const T& b){
if(a > b) return a = b, true; return false;
}
template<typename T> bool maximize(T& a, const T& b){
if(a < b) return a = b, true; return false;
}
const ll inf = 1e18;
struct line{
ll a, b, cnt, p;
line(ll a = 0, ll b = 0, ll cnt = 0, ll p = 0) : a(a), b(b), cnt(cnt), p(p) {}
ll eval(ll x){ return a * x + b; }
};
ll divi(ll a, ll b){
return a / b - ((a ^ b) < 0 && (a % b) != 0);
}
void isect(line& d1, line& d2){
if(d1.a == d2.a) d1.p = (d1.b > d2.b ? inf : -inf);
else d1.p = divi(d2.b - d1.b, d1.a - d2.a);
}
struct ConvexHullTrick{
deque<line> v;
ConvexHullTrick() : v() {}
void init(){
deque<line>().swap(v);
}
void add(line d){
d.p = inf;
if(!v.empty()) isect(v.back(), d);
while((int)v.size() > 1 && v[(int)v.size() - 2].p >= v.back().p){
v.pop_back();
isect(v.back(), d);
}
v.push_back(d);
}
pair<ll, int> query(ll x){
while((int)v.size() > 1){
ll l = v[0].eval(x);
ll r = v[1].eval(x);
if(l != r){
if(l > r) v.pop_front();
if(l < r) break;
} else{
if(v[0].cnt > v[1].cnt) v.pop_front();
else break;
}
}
return {v[0].eval(x), v[0].cnt};
}
} cht;
ll square(ll x){
return x * x;
}
long long take_photos(int n, int m, int k, std::vector<int> l, std::vector<int> r) {
vector<int> diagonal(n);
for(int i = 0; i < n; ++i){
if(l[i] > r[i]) swap(l[i], r[i]);
}
vector<int> pos(n);
iota(all(pos), 0);
sort(all(pos), [&](int i, int j){
if(l[i] != l[j]) return l[i] < l[j];
return r[i] > r[j];
});
int ptr = 0;
vector<pair<int, int>> after;
for(int i : pos){
int x = l[i], y = r[i];
after.push_back({x, y});
while(sz(after) > 1){
if(after[sz(after) - 2].first <= after.back().first && after[sz(after) - 2].second >= after.back().second){
after.pop_back();
} else break;
}
}
n = sz(after);
vector<ll> L(n), R(n);
for(int i = 0; i < n; ++i){
tie(L[i], R[i]) = after[i];
assert(i == 0 || (L[i - 1] <= L[i] && R[i - 1] <= R[i]));
--L[i]; //for (R[j] - L[i])^2 instead of (R[j] - L[i] + 1)^2
}
vector<ll> dp(n + 1);
vector<int> cnt(n + 1);
auto f = [&](ll lambda) -> pair<ll, int>{
cht.init();
for(int i = 0; i < n; ++i){
ll extra = square(max(0ll, R[i - 1] - L[i]));
cht.add(line(-2 * L[i], dp[i] + L[i] * L[i], cnt[i]));
pair<ll, int> q = cht.query(R[i]);
dp[i + 1] = q.first + R[i] * R[i];
cnt[i + 1] = q.second + 1;
}
return {dp[n], cnt[n]};
};
ll lo = 0, hi = 1e18, ans = 0;
while(lo <= hi){
ll mid = lo + hi >> 1;
pair<ll, int> eval = f(mid);
if(eval.second <= k) {
ans = mid, hi = mid - 1;
}
else lo = mid + 1;
}
pair<ll, int> ret = f(ans);
ll last = ret.first - k * ans;
return last;
}
#ifdef LOCAL
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout << take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6}) << '\n';
cout << take_photos(2, 6, 2, {1, 4}, {4, 1}) << '\n';
return 0;
}
#endif //LOCAL
