#include "aliens.h"

// Skyqwq
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> void inline read(T &x) {
    x = 0; int f = 1; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') { f = -1; } s = getchar(); }
    while (s >= '0' && s <= '9') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

template <typename T> bool inline chkMin(T &x, T y) { return y < x ? x = y, 1 : 0; }
template <typename T> bool inline chkMax(T &x, T y) { return y > x ? x = y, 1 : 0; }


const int N = 200005;

const LL INF = 0x3f3f3f3f3f3f3f3f;

int x[N], y[N], t, c[N];

LL f[N];

PII e[N];


LL ans = INF;

bool inline cmp(PII x, PII y) {
    if (x.fi == y.fi) return x.se > y.se;
    return x.fi < y.fi;
}

LL Y(int j) {
    return f[j] - 2ll * x[j + 1] + 1ll * x[j + 1] * x[j + 1];
}

LL X(int j) {
    return 2ll * x[j + 1];
}

typedef long double LD;

int q[N];

int get(LL m) {
    memset(f, 0x3f, sizeof f);
    memset(c, 0, sizeof c);
    f[0] = 0;
    int hh = 0, tt = 0;
    q[0] = 0;
    for (int i = 1; i < t; i++) {
        assert(x[i] < x[i + 1]);
        assert(y[i] < y[i + 1]);
    }
    for (int i = 1; i <= t; i++) {

        while (hh < tt) {
            LL A = Y(q[hh + 1]) - Y(q[hh]), B = y[i] * (X(q[hh + 1]) - X(q[hh]));
            if (A < B) hh++;
            else break;
        }
        int k = q[hh];
        LL w = f[k] + (y[i] - x[k + 1] + 1ll) * (y[i] - x[k + 1] + 1ll) - m;
        f[i] = w;
        assert(f[i] != INF);
        c[i] = c[k] + 1;
        if (f[i] != INF && i != t && y[i] >= x[i + 1]) f[i] -= (y[i] - x[i + 1] + 1ll) * (y[i] - x[i + 1] + 1ll); 
        if (i == t) break;
        bool ok = 1;
        while (hh < tt) {
            LL A = (Y(q[tt]) - Y(q[tt - 1])) * (X(i) - X(q[tt]));
            LL B = (Y(i) - Y(q[tt])) * (X(q[tt]) - X(q[tt - 1]));
            if (A > B) tt--;
            else break;
        }
        q[++tt] = i;
     }
     for (int i = 1; i <= t; i++) {
        assert(c[i - 1] <= c[i]);

     }
     return c[t];
}

long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> C) {
    for (int i = 0; i < R.size(); i++) {
        if (R[i] > C[i]) swap(R[i], C[i]);
        e[i + 1] = mp(R[i], C[i]);
    }
    sort(e + 1, e + 1 + n, cmp);
    for (int i = 1; i <= n; i++) {
        if (!t || e[i].se > y[t]) {
            ++t;
            x[t] = e[i].fi, y[t] = e[i].se;
        } 
    }

    chkMin(k, t);
    LL l = -1ll * m * m, r = 0;
    while (l < r) {
        LL mid = (l + r + 1) >> 1;
        if (get(mid) <= k) l = mid;
        else r = mid - 1; 
    }
    get(r);
    return (f[t] + k * r);
}