#include <bits/stdc++.h>

#define pub push_back
#define ll long long
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()

using namespace std;

#include "aliens.h"

const ll LINF = (ll)1e18 + 7;
const int INF = (int)1e9 + 7;

int h[1000007];
double dp[100007];
int p[100007];
vector<int> q, ss;
int n, m, k;

double getCross(double k1, double b1, double k2, double b2){
    return (double)(b2 - b1) / (double)(k1 - k2);
}

ll getDP(double cost){
    for (int i = 0; i < 100007; i++) dp[i] = LINF, p[i] = -1;

    vector<pair<pair<double, int>, pair<double, double> > > w;

    int uk = 0;

    w.pub(mp(mp(0, -1), mp(-2 * (ll)h[q[0]], (ll)h[q[0]] * (ll)h[q[0]])));

    for (int j = 0; j < q.size(); j++){
        while(uk + 1 < w.size() && w[uk + 1].x.x <= (q[j] + 1)) uk++;
        dp[j] = (double)(q[j] + 1) * w[uk].y.x + w[uk].y.y + (double)(q[j] + 1) * (double)(q[j] + 1) + cost;
        p[j] = w[uk].x.y;

        if (j == (int)q.size() - 1) continue;
        double kk = -2 * (double)h[q[j + 1]];
        double bb = dp[j] - max(0, q[j] - h[q[j + 1]] + 1) * (double)max(0, q[j] - h[q[j + 1]] + 1) + h[q[j + 1]] * (double)h[q[j + 1]];
        while(w.size()){
            double xx = getCross(kk, bb, w.back().y.x, w.back().y.y);
            if (xx > w.back().x.x){
                w.pub(mp(mp(xx, j), mp(kk, bb)));
                break;
            } else w.pop_back();
        }
        if (w.size() == 0) w.pub(mp(mp(0, j), mp(kk, bb)));
    }
    int ans = 0;
    int v = (int)q.size() - 1;
    while(1){
        if (v == -1) break;
        v = p[v];
        ans++;
    }
    return ans;
}

long long take_photos(int N, int M, int K, vector<int> x, vector<int> y) {
    n = N, m = M, k = K;
    for (int i = 0; i < n; i++){
        x[i]++, y[i]++;
    }
    for (int i = 0; i <= m; i++) h[i] = INF;
    for (int i = 0; i < n; i++){
        h[max(x[i], y[i])] = min(h[max(x[i], y[i])], min(x[i], y[i]));
        ss.pub(max(x[i], y[i]));
    }
    sort(all(ss));
    ss.resize(unique(ss.begin(), ss.end()) - ss.begin());
    for (int x : ss){
        while(q.size() && h[q.back()] >= h[x]) q.pop_back();
        q.pub(x);
    }

    double l = 0, r = (double)1e18;
    for (int i = 0; i < 100; i++){
        ll mm = (l + r) / (ll)2;
        if (getDP(mm) > k)
            l = mm;
        else
            r = mm;
    }
    getDP(r);

    return dp[(int)q.size() - 1] - (double)getDP(r) * r;
}