#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(false), cin.tie(NULL)
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll mod = 1e9 + 7;
// convex hull trick
struct CHT{
// y = ax + b
struct line{
ll a, b, cnt;
ll eval(ll x) const {
return a*x + b;
}
};
deque<line> dq;
// a와 b의 교점이 c의 교점보다 오른쪽에 있으면 true
static bool chk(line l1, line l2, line l3){
return (l2.b - l1.b) * (l1.a - l3.a) >= (l3.b - l1.b) * (l1.a - l2.a);
}
void insert(ll a, ll b, ll cnt){
line l = {a, b, cnt};
while(dq.size() >= 2 && chk(dq[dq.size() - 2], dq[dq.size() - 1], l))
dq.pop_back();
dq.push_back(l);
}
pll query(ll x){
while(dq.size() >= 2 && dq[0].eval(x) >= dq[1].eval(x))
dq.pop_front();
return {dq[0].eval(x), dq[0].cnt};
}
};
const ll INF = 1e18;
vector<pll> points;
// alien trick
vector<ll> dp(505050), cdp(505050);
ll cost(ll x, ll d){
ll ret = points[x+1].first * points[x+1].first;
if(x != -1) {
ll tmp = max(points[x].second - points[x + 1].first + 1, 0LL);
ret -= tmp * tmp;
}
return ret;
}
void solve(ll d){
ll n = points.size();
CHT cht;
ll a = -2 * points[0].first;
ll b = 2 * cost(-1, d) + d;
cht.insert(2 * a, b, 0);
for(int i = 0; i < n; i++){
auto [val, cnt] = cht.query(points[i].second + 1);
dp[i] = val + 2 * (points[i].second + 1) * (points[i].second + 1);
cdp[i] = cnt + 1;
if(i == n-1) break;
a = -2 * points[i+1].first;
b = 2 * cost(i, d) + dp[i] + d;
cht.insert(2 * a, b, cdp[i]);
}
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
for(int i = 0; i < n; i++){
int x = r[i], y = c[i];
if(x > y) swap(x, y);
points.emplace_back(x, y);
}
sort(points.begin(), points.end());
vector<pll> tp;
tp.push_back(points[0]);
for(int i = 1; i < n; i++){
while(!tp.empty() && tp.back().first == points[i].first)
tp.pop_back();
if(tp.empty() || tp.back().second < points[i].second)
tp.push_back(points[i]);
}
points = tp;
// for(auto [x, y] : points){
// cout << x << ' ' << y << endl;
// }
n = points.size();
k = min(n, k);
ll d = 0;
ll ans = 1e18;
ll begin = 0, end = (ll)m * (ll)m;
while(begin <= end){
ll mid = (begin + end) >> 1;
solve(2 * mid + 1);
if(cdp[n-1] <= k){
d = mid;
ans = dp[n-1] - k * (2 * d + 1);
end = mid - 1;
} else {
begin = mid + 1;
}
}
// cout << "d : " << d << endl;
solve(2 * d);
// cout << "cdp : " << cdp[n-1] << endl;
// for(int i = 0; i < n; i++) cout << dp[i] << ' ';
// cout << endl;
// for(int i = 0; i < n; i++) cout << cdp[i] << ' ';
// cout << endl;
ans = dp[n-1] - k * (2 * d);
// cout << ans << endl;
return ans / 2;
}
// int main() {
// fastio;
// int n, m, k;
// cin >> n >> m >> k;
// vector<int> r(n), c(n);
// for(int i = 0; i < n; i++)
// cin >> r[i] >> c[i];
// cout << take_photos(n, m, k, r, c);
// return 0;
// }
