#include "aliens.h"
#include <bits/stdc++.h>
#define mp make_pair
#define sz(x) ((int)((x).size()))
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ipair;
typedef pair <ll, ll> lpair;
const int IINF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double DINF = numeric_limits<double>::infinity();
const double DNAN = numeric_limits<double>::quiet_NaN();
const double EPS = 1e-9;
const double PI = acos((double)-1.0);
const int DX[] = { 1, 0, -1, 0, 1, -1, 1, -1};
const int DY[] = { 0, 1, 0, -1, 1, -1, -1, 1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll sqr(ll x) { return x*x; } ll sqr(int x) { return (ll)x*x; }
double sqr(double x) { return x*x; }
mt19937 mmtw(960172);
ll rnd(ll x, ll y) { static uniform_int_distribution<ll> d; return d(mmtw) % (y - x + 1) + x; }
template<typename T, typename M> T& updMin(T& a, M const& b) { if (b < a) a = b; return a; }
template<typename T, typename M> T& updMax(T& a, M const& b) { if (a < b) a = b; return a; }
ll divFloor(ll a, ll b) { if (b < 0) { a = -a; b = -b; } return a >= 0 ? a / b : (a - b + 1) / b; }
ll divCeil(ll a, ll b) { if (b < 0) { a = -a; b = -b; } return a >= 0 ? (a + b - 1) / b : a / b; }
ll divFloorS(ll a, ll b) { if (b < 0) { a = -a; b = -b; } return a >= 0 ? (a + b - 1) / b - 1 : a / b - 1; }
ll divCeilS(ll a, ll b) { if (b < 0) { a = -a; b = -b; } return a >= 0 ? a / b + 1 : (a - b + 1) / b + 1; }
template<typename T> T pw(T a, ll b) { T r = T(1); if (b <= 0) return r; for (;; b >>= 1) { if (b & 1) r *= a; if (b) a *= a; else return r; } }
template<typename T> void unique(vector<T> &a) { sort(all(a)); a.erase(unique(all(a)), a.end()); }
template<typename T> int lowerBound(vector<T> const& a, T const& x) { return lower_bound(all(a), x) - a.begin(); }
template<typename T> int upperBound(vector<T> const& a, T const& x) { return upper_bound(all(a), x) - a.begin(); }
template<typename K, typename V> V getOrDef(map<K, V> const& a, K const& k, V const& def = V()) { auto it = a.find(k); return it == a.end() ? def : it->second; }
template<typename K, typename V> V getOrDef(unordered_map<K, V> const& a, K const& k, V const& def = V()) { auto it = a.find(k); return it == a.end() ? def : it->second; }
template<typename T> T getOrDef(vector<T> const& a, int i, T const& def = T()) { return i < 0 || i >= sz(a) ? def : a[i]; }
template<typename T> T getOrDef(vector<vector<T>> const& a, int i, int j, T const& def = T()) { return i < 0 || i >= sz(a) ? def : getOrDef(a[i], j, def); }
template<typename T> T backOrDef(vector<T> const& a, T const& def = T()) { return a.empty() ? def : a.back(); }
template<typename A, typename B> istream& operator >> (istream& in, pair<A, B>& p) { return in >> p.X >> p.Y; }
template<typename A, typename B> ostream& operator << (ostream& out, pair<A, B> const& p) { return out << p.X << " " << p.Y; }
template<typename T> istream& operator >> (istream& in, vector<T>& a) { for (T& x : a) in >> x; return in; }
template<typename T> ostream& operator << (ostream& out, vector<T> const& a) {
bool f = true;
for (T const& x : a) {
if (!f) out << " ";
f = false; out << x;
}
return out;
}
template<typename T> ostream& operator << (ostream& out, vector<vector<T>> const& a) {
for (vector<T> const& x : a) out << x << "\n";
return out;
}
template<typename T> bool isZero(T const& x) { return x == T(0); }
bool isZero(float x) { return abs(x) < EPS; }
bool isZero(double x) { return abs(x) < EPS; }
bool isZero(long double x) { return abs(x) < EPS; }
template<typename T> int sgn(T const& x) { if (isZero(x)) return 0; return x > 0 ? 1 : -1; }
template<typename T>
class LinearMaxInc {
struct Seg {
T x0, k, b;
int index;
};
vector<Seg> segs;
public:
LinearMaxInc() = default;
explicit LinearMaxInc(vector<pair<T, T>> const& a) {
vector<int> order(sz(a));
iota(all(order), 0);
sort(all(order), [&](int x, int y) { return a[x].first < a[y].first; });
for (int i : order) add(a[i].first, a[i].second, i);
}
void add(T const& k, T const& b, int index = -1) {
assert(segs.empty() || segs.back().k <= k);
while (true) {
if (segs.empty()) {
segs.push_back({numeric_limits<T>::lowest(), k, b, index});
return;
}
Seg const& s = segs.back();
if (s.k == k) {
if (s.b >= b) return;
segs.pop_back();
continue;
}
T x0 = (s.b - b + (numeric_limits<T>::is_integer && s.b - b >= 0 ? k - s.k - 1 : 0)) / (k - s.k);
if (s.x0 >= x0)
segs.pop_back();
else {
segs.push_back({x0, k, b, index});
return;
}
}
}
pair<T, int> getMax(T const& x) const {
if (segs.empty()) return {numeric_limits<T>::lowest(), -1};
int cl = 0, cr = sz(segs);
while (cr - cl > 1) {
int mid = (cl + cr) / 2;
(x < segs[mid].x0 ? cr : cl) = mid;
}
return {segs[cl].k * x + segs[cl].b, segs[cl].index};
}
};
long long take_photos(int n, int, int k, std::vector<int> cx, std::vector<int> cy) {
vector<ipair> segs;
for (int i = 0; i < n; ++i) {
int x = cx[i], y = cy[i];
if (x > y) swap(x, y);
++y;
segs.push_back({x, y});
}
sort(all(segs), [](ipair const& a, ipair const& b) {
if (a.Y != b.Y) return a.Y < b.Y;
return a.X > b.X;
});
{
vector<ipair> segs2;
for (ipair s : segs) {
while (!segs2.empty() && segs2.back().X >= s.X)
segs2.pop_back();
segs2.push_back(s);
}
segs = move(segs2);
}
n = sz(segs);
k = min(k, n);
ll ans = -1;
ll cl = -1.1e12, cr = 1.1e12;
while (cr - cl > 1) {
ll lambda = (cl + cr) / 2;
vector<pair<ll, int>> d(n + 1);
d[0] = {0, 0};
LinearMaxInc<ll> lm;
for (int i = 0; i <= n; ++i) {
if (i != 0) {
auto nd = lm.getMax(segs[i - 1].Y);
d[i] = {-nd.X + sqr(segs[i - 1].Y) - lambda, nd.Y};
}
if (i != n) {
lm.add(2 * segs[i].X, -d[i].X + (i == 0 ? 0LL : sqr(max(0, segs[i - 1].Y - segs[i].X))) - sqr(segs[i].X), d[i].Y + 1);
}
}
updMax(ans, d[n].X + lambda * k);
if (d[n].Y < k)
cl = lambda;
else
cr = lambda;
}
return ans;
}
