#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
using namespace std;
#include "aliens.h"
int64_t dp[2][1000005];
vector<int> L(1000005);
vector<ii> item;
int64_t cost(int64_t l, int64_t r){
if(r < l) return 0;
return (r - l + 1) * (r - l + 1);
}
void dnc(int k, int l, int r, int optl, int optr){
if(r < l) return;
int mid = (l + r) / 2;
int opt = optl;
for(int i = optl; i <= optr && i <= mid; i++){
if(dp[k][mid] > dp[k - 1][i] + cost(L[i], item[mid].second) - cost(L[i], item[i].second)){
opt = i;
dp[k][mid] = dp[k - 1][i] + cost(L[i], item[mid].second) - cost(L[i], item[i].second);
}
}
dnc(k, l, mid - 1, optl, opt);
dnc(k, mid + 1, r, opt, optr);
}
long long take_photos(int m, int n, int k, std::vector<int> r, std::vector<int> c) {
item.pb({0, 0});
for(int i = 0; i < m; i++) item.pb({min(r[i], c[i])+1, max(r[i], c[i])+1});
m++;
sort(all(item), [&](ii a, ii b){return a.second < b.second;});
for(int i = 0; i <= m; i++) dp[0][i] = dp[1][i] = 1e18;
dp[0][0] = 0;
L[m - 1] = n + 1;
for(int r = m - 2; r >= 0; r--){
L[r] = min(L[r + 1], item[r + 1].first);
}
for(int i = 1; i <= k; i++){
dnc(1, 0, m - 1, 0, m - 1);
for(int r = 0; r < m; r++) dp[1][r] = min(dp[1][r], dp[0][r]);
for(int r = 0; r < m; r++){
swap(dp[0][r], dp[1][r]);
dp[1][r] = 1e18;
}
}
return dp[0][m - 1];
}
