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

using ll = long long;
using namespace std;

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);
            mx = r;
        }
    }

    auto square = [](auto P) -> ll {
        ll x = P.second - P.first + 1;
        if (x < 0) {
            return 0;
        }
        return x * x;
    };

    auto merge = [](auto P1, auto P2) -> pair<int, int> {
        return make_pair(max(P1.first, P2.first), min(P1.second, P2.second));
    };

    while (B.size() > k) {
        ll mn = INT32_MAX;
        int b = -1;

        for (int i = 1; i < (int)B.size(); i++) {
            ll x = B[i].second - B[i - 1].second;
            ll y = B[i].first - B[i - 1].first;
            if (mn > x * y) {
                b = i;
                mn = x * y;
            }
        }

        B[b - 1].second = B[b].second;
        B.erase(B.begin() + b);
    }

    ll cur = square(B[0]);

    for (int i = 1; i < (int)B.size(); i++) {
        cur += square(B[i]) - square(merge(B[i], B[i - 1]));
    }

    return cur;
}