#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define FILL(a, b) memset(a, b, sizeof(a))

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;

const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1e9 + 7;
const int MAX = 1e5 + 5;

ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
ll mul(ll a,ll b, ll M){if(b==0)return 0;ll t=mul(a,b/2,M);if(b&1)return (t+t+a)%M;return (t+t)%M;}
ll fpow(ll a, ll b, ll M){if(b==0)return 1;ll t=fpow(a,b/2,M);if(b&1)return mul(mul(t,t,M),a,M)%M;return mul(t,t,M)%M;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

vii p;
int L[MAX], R[MAX];
ll dp[MAX][2];

void go(int l, int r, int optl, int optr, int lvl) {
    if(l > r) {
        return;
    }
    int mid = (l+r)/2;
    int opt = -1;
    int cur = lvl&1, prev = !cur;
    for(int i = optl; i <= min(optr, mid); i++) {
        ll cst = dp[i-1][prev] + 1LL * (R[mid] - L[i]+1) * (R[mid]-L[i]+1) - (R[i-1]-L[i]+1 > 0 ? 1LL * (R[i-1]-L[i]+1) * (R[i-1] - L[i]+1) : 0LL);
        if(cst < dp[mid][cur]) {
            dp[mid][cur] = cst;
            opt = i;
        }
    }
    go(l, mid-1, optl, opt, lvl);
    go(mid+1, r, opt, optr, lvl);
    return;
}

ll take_photos(int n, int m, int k, int* r, int* c) {
    for(int i = 0; i < n; i++) {
        p.pb({min(r[i], c[i]), -max(r[i], c[i])});
    }
    sort(p.begin(), p.end());
    int idx = 1, max_val = -9999;
    for(int i = 0; i < n; i++) {
        if(-p[i].s > max_val) {
            L[idx] = p[i].f;
            R[idx] = -p[i].s;
            max_val = -p[i].s;
            idx++;
        }
    }
    idx--;
    R[0] = -1e9;
    for(int i = 1; i <= idx; i++) {
        dp[i][0] = 1e18;
    }
    for(int i = 1; i <= min(idx, k); i++) {
        int cur = i&1;
        for(int j = 1; j <= idx; j++) {
            dp[j][cur] = 1e18;
        }
        go(1, idx, 1, idx, i);
    }
    return dp[idx][min(idx, k)&1];
}