#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
const int maxn = 100003;
const double inf = 1/.0;
struct line
{
long long k, m, delta;
double p;
bool operator < (const long long &t) {return p < t;}
};
double intersection_point(line a, line b)
{
if (a.k == b.k)
return (a.m >= b.m ? -inf: inf);
else
return (double)(b.m - a.m) / (double)(a.k - b.k);
}
struct line_container
{
vector <line> lines;
void insert_line(long long a, long long b, long long delta)
{
line curr = {a, b, delta, 0};
while (!lines.empty() && intersection_point(curr, lines.back()) <= lines.back().p)
lines.pop_back();
if (!lines.empty())
curr.p = intersection_point(curr, lines.back());
else
curr.p = -inf;
lines.push_back(curr);
}
pair <long long, long long> query(long long pos)
{
auto it = lower_bound(lines.begin(), lines.end(), pos);
it--;
return {it->delta, it->k * pos + it->m};
}
};
vector <pair <long long, long long> > v;
line_container convex_hull;
long long dp[maxn];
long long delta[maxn];
void calc(long long x)
{
convex_hull.lines.clear();
dp[0] = 0;
delta[0] = 0;
convex_hull.insert_line(2 * v[0].first, -dp[0] - 1ll * v[0].first * v[0].first, 0);
for (int i = 1; i <= (int)v.size(); i++)
{
auto curr = convex_hull.query(v[i-1].second + 1);
dp[i] = -curr.second + (v[i-1].second + 1) * (v[i-1].second + 1) + x;
delta[i] = curr.first + 1;
if (i != (int)v.size())
{
long long curr_c = -dp[i] - v[i].first * v[i].first;
if (v[i-1].second >= v[i].first)
curr_c += (v[i-1].second - v[i].first + 1) * (v[i-1].second - v[i].first + 1);
convex_hull.insert_line(2 * v[i].first, curr_c, delta[i]);
}
}
}
long long take_photos(int n, int m, int k, vector <int> r, vector <int> c)
{
map <int, int> mp;
for (int i = 0; i < n; i++)
{
r[i]++;
c[i]++;
int ll = min(r[i], c[i]);
int rr = max(r[i], c[i]);
if (!mp.count(rr) || ll < mp[rr])
mp[rr] = ll;
}
for (auto i: mp)
{
while (!v.empty() && v.back().first >= i.second)
v.pop_back();
v.push_back({i.second, i.first});
}
long long low = -1e12, high = 1e12;
while (high - low > 1)
{
long long mid = (low + high) / 2;
calc(mid);
if (delta[(int)v.size()] >= k)
low = mid;
else
high = mid;
}
low++;
calc(low);
return dp[(int)v.size()] - max(1ll * delta[(int)v.size()] * low, 1ll * k * low);
}
/*
int n, k, m;
vector <int> r, c;
int main()
{
cin >> n >> k >> m;
r.resize(n), c.resize(n);
for (int i = 0; i < n; i++)
cin >> r[i] >> c[i];
cout << take_photos(n, m, k, r, c) << endl;
}
*/
