#include "aliens.h"
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
deque<pll> cht;
deque<ll> cc;
void ins(pll line, ll cnt) {
while (cht.size()) {
if (cht.front().first == line.first && cht.front().second >= line.second) cht.pop_front(), cc.pop_front();
else if (cht.size() > 1 && (cht[1].second - cht[0].second)*(line.first - cht[1].first) >= (cht[0].first - cht[1].first)*(cht[1].second - line.second)) cht.pop_front(), cc.pop_front();
else break;
}
cht.push_front(line);
cc.push_front(cnt);
}
pll qu(ll x) {
while (cht.size() > 1) {
pll tmp = cht.back();
cht.pop_back();
if (cht.back().first * x + cht.back().second > tmp.first * x + tmp.second) {cht.push_back(tmp); break;}
cc.pop_back();
}
return {cht.back().first * x + cht.back().second, cc.back()};
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
ll cma[m];
vector<pll> v;
iloop(0, m) cma[i] = INF;
iloop(0, n) {
cma[max(r[i], c[i])] = min({cma[max(r[i], c[i])], (ll)r[i], (ll)c[i]});
}
iloop(m-1, -1) {
if (cma[i] == INF) continue;
if (!v.size() || v.back().second > cma[i]) v.push_back({i, cma[i]});
}
reverse(v.begin(), v.end());
ll lb = 0, ub = INF, mid;
n = v.size();
iloop(0, n) v[i].first++;
pll dp[n+1];
while (lb < ub) {
mid = (lb + ub) >> 1;
dp[0] = {0, 0};
cht.clear();
cc.clear();
iloop(0, n) {
ll disc = (i ? max(v[i-1].first - v[i].second, 0LL) : 0);
ins({-2 * v[i].second, dp[i].first + v[i].second * v[i].second - disc*disc}, dp[i].second);
pll tm = qu(v[i].first);
dp[i+1] = {tm.first + v[i].first * v[i].first + mid, tm.second + 1};
// dp[i] = min(dp[j-1] + (v[i].first + 1 - v[j].second)^2)
}
if (dp[n].second <= k) ub = mid;
else lb = mid + 1;
}
//cout << lb << endl;
dp[0] = {0, 0};
cht.clear();
cc.clear();
iloop(0, n) {
//cout << dp[i].second << ";";
ll disc = (i ? max(v[i-1].first - v[i].second, 0LL) : 0);
ins({-2 * v[i].second, dp[i].first + v[i].second * v[i].second - disc*disc}, dp[i].second);
pll tm = qu(v[i].first);
//cout << tm.second << endl;
dp[i+1] = {tm.first + v[i].first * v[i].first + lb, tm.second + 1};
// dp[i] = min(dp[j-1] + (v[i].first + 1 - v[j].second)^2)
//cout << dp[i+1].first << "," << dp[i+1].second << endl;
}
assert(dp[n].second <= k);
//iloop(0, n) cout << v[i].first << " " << v[i].second << endl;
//iloop(0, n+1) cout << dp[i].first << "," << dp[i].second << endl;
return dp[n].first - lb*dp[n].second;
}
