#include <bits/stdc++.h>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifndef ONLINE_JUDGE
#define w(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#define MAXN (long long int) (1e5 + 5)
#else
#define w(...)
#define MAXN (long long int) (1e5 + 5)
#endif
// DEFINES/MACROS
#define pb push_back
#define st first
#define nd second
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define ROF(i,a,b) for(int i = (a); i >= (b); --i)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
// TYPEDEFS
typedef long long int ll;
typedef vector<ll> vi;
typedef set<ll> si;
typedef pair<ll, ll> pll;
template<typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxheap = priority_queue<T>;
template<typename T>
using vec = vector<T>;
// CONSTS
const ll inf = 1e18;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const string yes = "YES";
const string no = "NO";
const string yesn = "YES\n";
const string non = "NO\n";
const string nl = "\n";
struct Line {
mutable ll k, m, p, taken;
bool operator<(const Line& o) const {
if (k == o.k) return taken > o.taken;
return k < o.k;
}
bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> { // -(x - i)^2
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
static const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) return x->p = inf, 0;
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m, ll t) { // INVERTED SIGNS, WILL FIND MINIMUM
auto z = insert({-k, -m, 0, t}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
pll query(ll x) {
assert(!empty());
auto l = *lower_bound(x);
return {-l.k * x - l.m, l.taken};
}
};
ll take_photos(int n, int m, int k, vec<int> r, vec<int> c) { //
vec<pll> intervals(n);
for (ll i = 0; i < n; i++) {
auto [x, y] = minmax(r[i], c[i]);
intervals[i] = {x, y};
}
sort(all(intervals), [&](const pll& a, const pll& b) {
if (a.st != b.st) return a.st < b.st;
return a.nd > b.nd;
});
vi jmps(m+1);
ll rightendpoint = -1;
for (auto [l, r] : intervals) {
if (r <= rightendpoint) continue;
rightendpoint = r;
jmps[l] = r+1;
}
auto get = [&](ll lambda)->ll {
vec<pll> dp(m+1, {inf, 0});
LineContainer CHT; // gets minimum
ll maxr = 0;
dp[0] = {0, 0};
for (ll i = 0; i < m; i++) {
ll savable = max(maxr - i, 0ll);
ll saved = savable*savable;
CHT.add(-2*i, i*i + dp[i].st - saved, -dp[i].nd);
if (jmps[i]) {
ll r = jmps[i];
pll best = CHT.query(r);
maxr = r;
ll cost = best.st + r*r + lambda;
ll taken = best.nd + 1;
dp[i+1] = min(dp[i+1], {cost, -taken});
}
else {
dp[i+1] = min(dp[i+1], dp[i]);
}
}
if (-dp[m].nd <= k) { // is no of segments valid?
assert(dp[m].st - lambda * (-dp[m].nd) >= 0);
return dp[m].st - lambda * (-dp[m].nd);
}
else return -1;
};
ll lo = 0;
ll hi = 1ll*m*m + 1;
ll ans = inf;
while (lo <= hi) {
ll lamb = (lo+hi)/2;
ll res;
if ((res = get(lamb)) >= 0) {
ans = min(ans, res);
hi = lamb - 1;
}
else lo = lamb + 1;
}
return ans;
}
