#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
const int inf = 1e9;
const ll inf64 = 1e18;
struct output {
ll res;
void print() {
cout << res << "\n";
}
bool operator == (const output& o) const {
return res == o.res;
}
};
struct input {
int n, m, k;
vector<pii> a;
input() = default;
void read() {
cin >> n >> m >> k;
a.resize(n);
for (auto& [x, y] : a)
cin >> x >> y;
}
void print() {
cout << n << " " << m << " " << k << "\n";
for (auto [x, y] : a)
cout << x << " " << y << "\n";
}
void gen() {
static mt19937 rnd(42);
const int MAXN = 100;
n = rnd() % MAXN + 1;
m = rnd() % MAXN + 1;
k = rnd() % n + 1;
a.resize(n);
for (auto& [x, y] : a) {
x = rnd() % m;
y = rnd() % m;
}
}
void gen_max_test() {
}
void prepare() {
for (auto& [x, y] : a) {
if (y > x)
swap(x, y);
}
vector<pii> st;
sort(a.begin(), a.end());
for (int i = 0; i < n; i++) {
if (i > 0 && a[i].first == a[i - 1].first)
continue;
while (!st.empty() && st.back().second >= a[i].second)
st.pop_back();
st.push_back(a[i]);
}
a = st;
n = (int) a.size();
}
ll f(int len) {
return 1ll * len * len;
}
struct Line {
ll k = 0;
ll b = 0;
int c = 0;
ld intersect(const Line& o) const {
return ld(o.b - b) / ld(k - o.k);
}
ll f(ll x) const {
return k * x + b;
}
};
output fast() {
prepare();
vector<ll> rem(n);
for (int j = 0; j < n; j++)
rem[j] = f(max(0, (j > 0 ? a[j - 1].first : -1) - a[j].second + 1));
vector<pair<ll, int>> dp(n);
vector<Line> lines(n);
for (int j = 0; j < n; j++) {
lines[j] = {
-2ll * a[j].second,
(j > 0 ? dp[j - 1].first : 0ll) + 1ll * a[j].second * a[j].second - rem[j]
};
}
auto calc = [&](ll lambda) -> pair<ll, int> {
deque<Line> st;
for (int i = 0; i < n; i++) {
dp[i] = {inf64, inf};
ll CONST = lambda + 1ll * (a[i].first + 1) * (a[i].first + 1);
ll x0 = a[i].first + 1;
lines[i] = {
-2ll * a[i].second,
(i > 0 ? dp[i - 1].first : 0ll) + 1ll * a[i].second * a[i].second - rem[i],
(i > 0 ? dp[i - 1].second : 0)
};
while ((int) st.size() >= 2) {
Line L1 = st[(int) st.size() - 2];
Line L2 = st[(int) st.size() - 1];
if (L1.intersect(L2) < L2.intersect(lines[i]))
break;
st.pop_back();
}
st.push_back(lines[i]);
while ((int) st.size() >= 2 && st[0].intersect(st[1]) < x0)
st.pop_front();
dp[i] = {
CONST + st[0].f(x0),
st[0].c - 1
};
if ((int) st.size() > 1) {
dp[i] = min(dp[i], make_pair(CONST + st[1].f(x0), st[1].c - 1));
}
// for (Line line : st) {
// dp[i] = min(dp[i], make_pair(
// CONST + line.f(x0),
// line.c - 1
// ));
// }
// for (int j = i; j >= 0; j--) {
// dp[i] = min(dp[i], make_pair(
// CONST + lines[j].k * x0 + lines[j].b,
// lines[j].c - 1
// ));
// }
}
return dp[n - 1];
};
ll bl = 0, br = 1ll * m * m + 10, bm;
while (br - bl > 1) {
bm = bl + (br - bl) / 2;
auto tmp = calc(bm);
if (-tmp.second >= k) bl = bm;
else br = bm;
}
ll lambda = bl;
auto tmp = calc(lambda);
ll res = tmp.first - lambda * k;
return output{res};
}
output slow() {
#ifndef DEBUG
throw;
#endif
prepare();
vector<vector<ll>> dp(n, vector<ll>(k + 1, inf64));
for (int i = 0; i < n; i++) {
for (int j = i; j >= 0; j--) {
ll cost =
f(a[i].first - a[j].second + 1) -
f(max(0, (j > 0 ? a[j - 1].first : -1) - a[j].second + 1));
for (int c = 1; c <= k; c++)
dp[i][c] = min(dp[i][c], (j > 0 ? dp[j - 1][c - 1] : 0) + cost);
}
}
ll res = inf64;
for (int c = 1; c <= k; c++)
res = min(res, dp[n - 1][c]);
return output{res};
}
};
void test_case() {
input in;
in.read();
output res = in.fast();
res.print();
}
void work() {
int t = 1;
while (t--)
test_case();
}
void test() {
for (int t = 1;;t++) {
input in;
in.gen();
input in_fs = in;
input in_sl = in;
output fs = in_fs.fast();
output sl = in_sl.slow();
if (fs == sl) {
cout << "OK" << endl;
fs.print();
cout << "\n=========" << endl;
} else {
cout << "WA " << t << "\n";
cout << "exp\n";
sl.print();
cout << "\n=========\n";
cout << "fnd\n";
fs.print();
cout << "\n=========\n";
in.print();
break;
}
}
}
void max_test() {
input in;
in.gen_max_test();
input in_fs = in;
output fs = in_fs.fast();
fs.print();
}
#ifdef DEBUG
int main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
work();
// test();
// max_test();
return 0;
}
#else
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
input in;
in.n = n;
in.m = m;
in.k = k;
in.a.resize(n);
for (int i = 0; i < n; i++)
in.a[i] = {r[i], c[i]};
output fs = in.fast();
return fs.res;
}
#endif
