#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt")
using ll = long long int;
using ull = unsigned long long int;
using vi = vector<ll>;
using ii = pair<ll,ll>;
using vii = vector<ii>;
using ld = long double;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree < T, null_type, less<T>,
rb_tree_tag,
tree_order_statistics_node_update >;
//#ifdef SA_DEBUG
template <class T>
void print(T a) {cerr << a << endl;}
template <class T, class... V>
void print(T a, V... b) {cerr << a << ", "; print(b...);}
#define dbg(...) cerr << "[" << __LINE__ << "] " << #__VA_ARGS__ << " :: ", print(__VA_ARGS__)
//#else
//#define dbg(...) 7
//#endif
#define eb emplace_back
#define fi first
#define se second
const ll INFL = 1e18;
const int INF = 1e9;
const double PI = acos(-1);
const ll mod = 1e9+7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T, class V>
ostream& operator << (ostream &s, pair<T, V> a){
s << a.fi << ' ' << a.se; return s;
}
template<class T, class V>
istream& operator >> (istream &s, pair<T, V> &a){
s >> a.fi >> a.se; return s;
}
template<class T>
ostream& operator << (ostream &s, vector<T> a){
for(int i = 0; i < (int)a.size(); i++){
if(i > 0)s << ' ' ;
s << a[i];
} return s;
}
template<class T>
istream& operator >> (istream &s, vector<T> &a){
for(T &x : a)s >> x;
return s;
}
template<class T>
void input(T a[], int l, int r, istream &s = cin){
while(l <= r)s >> a[l++];
}
template<class T>
void output(T a[], int l, int r, bool en = true, ostream &s = cout){
while(l <= r){ s << a[l++];
if(l <= r) s << ' ';
} if(en)s << "\n";
}
const ll K = 1e4;
long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> C) {
vector<ii> v(n);
for(int i = 0; i < n; i++){
v[i] = {R[i], C[i]};
if(v[i].fi > v[i].se)swap(v[i].fi, v[i].se);
v[i].se = -v[i].se;
}
sort(v.begin(), v.end());
vector<ii> V(1, ii(-1, -1));
for(auto x : v){
ll l, r;
tie(l, r) = x;
r = -r;
if(V.back().se < r){
V.eb(l, r);
}
}
n = V.size();
auto cost = [&](int i, int j){
ll cst = V[j].se - V[i].fi + 1;
cst = cst * cst;
if(i > 0 && V[i - 1].se >= V[i].fi){
ll temp = (V[i - 1].se - V[i].fi + 1);
cst -= temp * temp;
}
return cst * K;
};
//dbg(V);
auto solve = [&](ll extra){
deque<ii> opt(1, ii(0, 1));
vi dp(n);
vector<int> cnt(n);
auto getVal = [&](int i, int j){
return dp[i] + cost(i + 1, j);
};
auto cmp = [&](int i, int j, int l){
return getVal(i, l) >= getVal(j, l);
};
for(int i = 1; i < n; i++){
//dp[i] = INFL;
//for(int j = 0; j < i; j++){
//ll x = getVal(j, i) + extra;
//if(x < dp[i])dp[i] = x, cnt[i] = cnt[j] + 1;
//}
assert(opt[0].se == i);
//dbg(i);
//for(auto x : opt)dbg(x);
dp[i] = getVal(opt[0].fi, i) + extra;
cnt[i] = cnt[opt[0].fi] + 1;
opt[0].se++;
while(opt.size() > 1 && opt[0].se >= opt[1].se)opt.pop_front();
while(!opt.empty() && cmp(opt.back().fi, i, opt.back().se))
opt.pop_back();
if(opt.empty()){
opt.eb(i, i + 1);
continue;
}
int lo = opt.back().se + 1, hi = n;
while(lo < hi){
int mid = (lo + hi) / 2;
if(cmp(opt.back().fi, i, mid))hi = mid;
else lo = mid + 1;
}
if(hi < n)opt.eb(i, lo);
}
return ii(dp[n - 1], cnt[n - 1]);
};
ll lo = 0, hi = 1e15;
//for(int i = lo; i <= hi; i++)dbg(solve(i));
//dbg(solve(20001));
//dbg(solve(20000));
//dbg(solve(19999));
//return 0;
while(lo < hi){
ll mid = (lo + hi) >> 1;
if(solve(mid).se > k)lo = mid + 1;
else hi = mid;
}
ll a, b, c, d;
tie(a, b) = solve(lo);
//tie(c, d) = solve(lo + 1);
//if(d < k)k = b;
//assert(a % K == lo * k % K);
return (a - lo * k + K - 1) / K;
}
/*
5 7 2
0 3
4 4
4 6
4 5
4 6
2 6 2
1 4
4 1
*/
