#pragma once
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;
struct seg
{
int l, r;
};
bool cmp(seg a, seg b)
{
if (a.l == b.l) return a.r > b.r;
return a.l < b.l;
}
void upd(ll& a, ll b)
{
a = min(a, b);
}
ll sq(ll x)
{
return x * x;
}
struct line
{
ld a, b; // a x + b
int val;
ld eval(ld x) { return a * x + b; }
};
ld inter(line a, line b) // prvy moment ked b zacne byt mensia ako a (b ma mensi slope inak)
{
// b.a * x + b.b < a.a * x + a.b -> x < (a.b - b.b) / (b.a - a.a)
if (abs(b.a - a.a) < 1e-9) return -1;
return (ld)(a.b - b.b) / (ld)(b.a - a.a);
}
vector<line> cht;
void add(line a)
{
while (cht.size() >= 2 && inter(cht.end()[-2], cht.end()[-1]) > inter(cht.end()[-2], a)) cht.pop_back();
while (cht.size() >= 1 && inter(cht.end()[-1], a) < 0) cht.pop_back();
cht.push_back(a);
}
int id = 0;
line mini(ld x)
{
id = max(0, min((int)cht.size() - 2, id));
while (id + 1 < cht.size() && cht[id + 1].eval(x) < cht[id].eval(x)) id++;
return cht[id];
}
void upd(pair<ld, int>&a, pair<ld, int> b) { a = min(a, b); }
pair<ld, int> eval(vector<seg> v, ld price)
{
cht.clear(), id = 0;
int n = v.size();
vector<pair<ld, int> > dp(n);
add({ 0, (ld)sq(v.back().r + 1) });
for (int r = 0; r < n; r++)
{
dp[r] = { sq(v[r].r - v[0].l + 1) + price, 1 };
line l = mini(v[r].r);
upd(dp[r], { l.eval(v[r].r) + sq(v[r].r) + price, l.val + 1 });
if (r == n - 1)
return dp[r];
line nw;
nw.a = -2. * (v[r + 1].l - 1);
nw.b = dp[r].first + sq(v[r + 1].l - 1) - sq(max(0, v[r].r - v[r + 1].l + 1));
nw.val = dp[r].second;
add(nw);
}
}
long long take_photos(int n, int m, int k, vector<int> l, vector<int> r)
{
vector<seg> v;
for (int i = 0; i < n; i++)
{
if (r[i] < l[i]) swap(l[i], r[i]);
v.push_back({ l[i], r[i] });
}
sort(v.begin(), v.end(), cmp);
vector<seg> v2;
for (seg i : v) if (v2.empty() || v2.back().r < i.r) v2.push_back(i);
v = v2;
n = v.size();
k = min(k, n);
ld lo = 0., hi = sq(m);
for (int it = 0; it < 100; it++)
{
ld mi = (lo + hi) / 2.;
if (eval(v, mi).second > k) lo = mi;
else hi = mi;
}
pair<ld, int> p = eval(v, hi);
p.first -= (ld)k * hi;
return (ll)(p.first + 0.3);
}
