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

#include "aliens.h"

#include <bits/stdc++.h>

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);

    constexpr int64_t G = 2e6;
    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);
            }
        }

        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;
}