#include "bits/stdc++.h"
#include "aliens.h"

using ll = long long;
using namespace std;

static constexpr ll INF = 1e15;

struct convex_hull_trick {

    struct Line {
        ll k = 0, b = 0;

        int i = 0;

        Line() = default;
        Line(ll k, ll b, int i) : k(k), b(b), i(i) {}

        ll get(ll x) const {
            return k * x + b;
        }
    };

    vector<pair<Line, int>> container;

    convex_hull_trick() = default;

    void add(ll k, ll b, int i) {
        Line A(k, b, i);
        
        while (!container.empty()) {
            auto [B, k] = container.back();
            
            ll x = (B.b - A.b) / (A.k - B.k);

            if (x <= k) {
                container.pop_back();
            } else {
                container.emplace_back(A, x);
                break;
            }
        }

        if (container.empty()) {
            container.emplace_back(A, -INF);
        }
    }

    Line get(ll x) const {
        auto it = prev(upper_bound(container.begin(), container.end(), x, [](ll x, auto A) {
            return A.second <= x;
        }));
        return it->first;
    }
};

ll take_photos(int n, int m, int k, vector<int> R, vector<int> C) {
    vector<pair<int, int>> A;

    for (int i = 0; i < n; i++) {
        A.emplace_back(min(R[i], C[i]), max(R[i], C[i]));
    }

    sort(A.begin(), A.end(), [](auto A, auto B) -> bool {
        return A.first < B.first || (A.first == B.first && A.second > B.second);
    });

    vector<pair<int, int>> B;

    int mx = -1;

    for (auto [l, r] : A) {
        if (mx < r) {
            B.emplace_back(l, r + 1);
            mx = r;
        }
    }

    auto calc = [&](ll cost) -> pair<ll, int> {
        convex_hull_trick cht;

        int m = (int)B.size();

        cht.add(-2 * B[0].first, 1ll * B[0].first * B[0].first + cost, 1);

        for (int i = 0; i < (int)B.size(); i++) {
            auto L = cht.get(B[i].second);

            ll val = L.get(B[i].second) + 1ll * B[i].second * B[i].second;
            int cnt = L.i;
            
            if (i + 1 < (int)B.size()) {
                ll s = max(0, B[i].second - B[i + 1].first);
                s *= s;

                cht.add(-2 * B[i + 1].first, val - s + 1ll * B[i + 1].first * B[i + 1].first + cost, i + 1);
            } else {
                return make_pair(val, cnt);
            }
        }
    };

    if (B.size() <= k) {
        return calc(0).first;
    }

    ll l = 0, r = INF;

    while (r - l > 1) {
        ll m = (l + r) / 2;
        
        if (calc(m).second >= k) {
            l = m;
        } else {
            r = m;
        }
    }

    auto ans = calc(l);

    return ans.first - l * k;
}