#pragma GCC optimize("O3")
#pragma GCC target("avx2")

#include "aliens.h"

#include <bits/stdc++.h>

constexpr int64_t G = 2e6;
struct Shit {
    int64_t p, d;  // y = (x - p)^2 * G + d

    int64_t get(int64_t x) const {
        return (x - p) * (x - p) * G + d;
    }
};

struct Node {
    Shit sh;
    Node *left, *right;

    Node() : sh{0, (int64_t)4e18}, left(nullptr), right(nullptr) { ; }
};

// constexpr int L = 0, R = 1.01e6;
void add(Node*& root, Shit sh, int l = 0, int r = 1.01e6) {
    if (l >= r) {
        return;
    }
    if (!root) {
        root = new Node();
        root->sh = sh;
        return;
    }
    int m = (l + r) / 2;
    if (sh.get(m) < root->sh.get(m)) {
        std::swap(sh, root->sh);
    }
    if (root->sh.p == sh.p) {
        return;
    } else {
        if (root->sh.p > sh.p) {
            add(root->left, sh, 0, m);
        } else {
            add(root->right, sh, m + 1, r);
        }
    }
}

int64_t get_min(const Node* root, int x, int l = 0, int r = 1.01e6) {
    int64_t res = 8e18;
    while (root) {
        int m = (l + r) / 2;
        res = std::min(res, root->sh.get(x));
        if (x < m) {
            root = root->left;
            r = m;
        } else if (x > m) {
            root = root->right;
            l = m + 1;
        } else {
            break;
        }
    }
    return res;
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    std::vector<std::pair<int, int>> input(n);
    for (int i = 0; i < n; i++) {
        input[i] = {r[i], c[i]};
    }
    for (auto& [x, y] : input) {
        if (x > y) {
            std::swap(x, y);
        }
    }
    // std::sort(input.begin(), input.end(), [&](auto a, auto b) { return a.first + a.second < b.first + b.second; });
    std::sort(input.begin(), input.end(), [&](auto a, auto b) {
        std::swap(a.second, b.second);
        return a < b;
    });

    int max = -1;
    for (auto& [x, y] : input) {
        if (y <= max) {
            x = y = -1;
            continue;
        }
        max = std::max(max, y);
    }
    input.erase(std::remove(input.begin(), input.end(), std::pair{-1, -1}), input.end());
    n = input.size();
    k = std::min(k, n);

    auto get = [&](int64_t fine) -> std::pair<int64_t, int> {
        std::vector<int64_t> dp(n + 1, 8e18);
        dp[0] = 0;
        // for (int i = 0; i < n; i++) {
        //     int64_t a = input[i].first;
        //     int64_t c = i == 0 ? -1 : input[i - 1].second;
        //     c = std::max(c, a - 1) + 1;
        //     int64_t dlt = dp[i] - (c - a) * (c - a) * G + fine * G;

        //     for (int j = i; j < n; j++) {
        //         int64_t b = input[j].second;
        //         int64_t cost = (b - a + 1) * (b - a + 1) * G + dlt;
        //         dp[j + 1] = std::min(dp[j + 1], cost + 1);
        //     }
        // }

        Node* nd = nullptr;
        for (int i = 0; i <= n; i++) {
            if (i > 0) {
                int64_t mn = get_min(nd, input[i - 1].second);
                dp[i] = mn + 1;
                if (i == n) {
                    break;
                }
            }

            int64_t a = input[i].first;
            int64_t c = i == 0 ? -1 : input[i - 1].second;
            c = std::max(c, a - 1) + 1;
            int64_t dlt = dp[i] - (c - a) * (c - a) * G + fine * G;

            add(nd, Shit{a - 1, dlt});
        }

        int64_t val = dp[n] / G;
        int cnt = dp[n] % G;
        return {val, cnt};
    };

    int64_t beg = -1, end = int64_t(m + 5) * (m + 5);
    while (beg + 1 < end) {
        int64_t mid = (beg + end) / 2;
        auto [val, cnt] = get(mid);
        if (cnt <= k) {
            end = mid;
        } else {
            beg = mid;
        }
    }

    int64_t res = get(end).first - k * end;

    return res;
}