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

    std::vector<int64_t> dp(n + 1, 1e18);
    dp[0] = 0;
    for (int t = 0; t < k; t++) {
        std::vector<int64_t> dp2(n + 1, 1e18);
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int64_t a = input[i].first;
                int64_t b = input[j].second;
                int64_t c = i == 0 ? -1 : input[i - 1].second;
                c = std::max(c, a - 1) + 1;

                assert(c <= b);
                int64_t cost = (b - a + 1) * (b - a + 1) - (c - a) * (c - a);
                dp2[j + 1] = std::min(dp2[j + 1], dp[i] + cost);
            }
        }
        dp = dp2;
    }
    int64_t res = dp[n];
    return res;
}