#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
long long take_photos(int n, int m, int k, vector<int> l, vector<int> r)
{
vector<int> cv(m);
for (int i = 0; i < m; i++)
{
cv[i] = i + 1;
}
for (int i = 0; i < n; i++)
{
int x = min(l[i], r[i]);
int y = max(l[i], r[i]);
cv[y] = min(cv[y], x);
}
l.clear();
r.clear();
for (int i = 0; i < m; i++)
{
if (cv[i] <= i)
{
while (l.size() && l.back() >= cv[i])
l.pop_back(), r.pop_back();
l.push_back(cv[i]), r.push_back(i);
}
}
n = l.size();
const long long INFLL = 1e18;
long long L = 0, R = m * m + 222;
long long ans = INFLL;
while (L + 1 < R)
{
long long M = (L + R) / 2;
vector<long long> dp(n, INFLL);
vector<long long> bl(n, INFLL);
for (int i = 0; i < n; i++)
dp[i] = M + (r[i] - l[0] + 1) * (r[i] - l[0] + 1), bl[i] = 1;
struct line{
long long k, b, id;
};
vector<line> convex;
for (int i = 0; i < n; i++)
{
long long res = 1ll * r[i] * r[i];
long long d = INFLL, used = 0;
for (auto e : convex)
{
if (e.b + e.k * r[i] < d)
d = e.b + e.k * r[i], used = INFLL;
if (e.b + e.k * r[i] == d && bl[e.id] < used)
used = bl[e.id];
}
res += d;
if (res < dp[i])
dp[i] = res, bl[i] = used + 1;
if (i + 1 < n)
{
long long b = dp[i] + 1ll * l[i + 1] * l[i + 1] + 1 - 2 * l[i + 1] + M + 1ll * max(0, r[i] - l[i + 1] + 1) * max(0, r[i] - l[i + 1] + 1);
long long k = 2 * (1 - l[i + 1]);
convex.push_back({k, b, i});
}
}
//cout << M << " " << dp[n - 1] << " " << bl[n - 1] << endl;
if (bl[n - 1] <= k)
ans = min(ans, dp[n - 1] - bl[n - 1] * M);
if (bl[n - 1] >= k)
L = M;
else
R = M;
}
L = 0, R = m * m + 222;
while (L + 1 < R)
{
long long M = (L + R) / 2;
vector<long long> dp(n, INFLL);
vector<long long> bl(n, INFLL);
for (int i = 0; i < n; i++)
dp[i] = M + (r[i] - l[0] + 1) * (r[i] - l[0] + 1), bl[i] = 1;
struct line{
long long k, b, id;
};
vector<line> convex;
for (int i = 0; i < n; i++)
{
long long res = 1ll * r[i] * r[i];
long long d = INFLL, used = 0;
for (auto e : convex)
{
if (e.b + e.k * r[i] < d)
d = e.b + e.k * r[i], used = INFLL;
if (e.b + e.k * r[i] == d && bl[e.id] < used)
used = bl[e.id];
}
res += d;
if (res < dp[i])
dp[i] = res, bl[i] = used + 1;
if (i + 1 < n)
{
long long b = dp[i] + 1ll * l[i + 1] * l[i + 1] + 1 - 2 * l[i + 1] + M + 1ll * max(0, r[i] - l[i + 1] + 1) * max(0, r[i] - l[i + 1] + 1);
long long k = 2 * (1 - l[i + 1]);
convex.push_back({k, b, i});
}
}
//cout << M << " " << dp[n - 1] << " " << bl[n - 1] << endl;
if (bl[n - 1] <= k)
ans = min(ans, dp[n - 1] - bl[n - 1] * M);
if (bl[n - 1] > k)
L = M;
else
R = M;
}
return ans;
}
