#include<bits/stdc++.h>
#include "aliens.h"
using namespace std;
using ll = long long;
const ll C = 2e6 + 10;
const ll N = 1e5 + 10;
const ll inf = 1e18;
struct Line {
ll m, b;
ll operator()(ll x) {return m*x + b;}
};
struct Node {
Line seg;
Node *lson, *rson;
int l=-C, r=C;
Node(Line s) {
seg = s;
lson = NULL, rson = NULL;
}
};
void insert(Line seg, Node* root) {
if(root->l + 1 == root->r) {
if(seg(root->l) < root->seg(root->l))root->seg = seg;
}
int mid = (root->l+root->r)/2;
if(root->seg(mid) < seg(mid))swap(root->seg, seg);
if(root->seg(mid) > seg(mid)) {
swap(seg, root->seg);
if(root->rson)insert(seg, root->rson);
else root->rson = new Node(seg);
}
else {
if(root->lson)insert(seg, root->lson);
else root->lson = new Node(seg);
}
}
ll query(int x, Node* root) {
if(root == NULL)return -inf;
if(root->l+1==root->r)return root->seg(x);
int mid = (root->l+root->r)/2;
if(x < mid) {
return max(root->seg(x), query(x, root->lson));
}
else return max(root->seg(x), query(x, root->rson));
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
for(int i = 0;i<n;i++) {
if(r[i] > c[i]) {
swap(r[i], c[i]);
}
}
vector<pair<int,int>> v;
{
vector<pair<long long, long long>> d;
for(int i = 0;i<n;i++)d.push_back(make_pair(r[i], -c[i]-1));
sort(d.begin(), d.end());
for(int i = 0;i<n;i++)d[i].second*=-1;
long long mxr = -inf;
for(int i = 0; i<n; i++) {
if(d[i].second > mxr) {
v.push_back(make_pair(d[i].second, d[i].first));
mxr = d[i].second;
}
}
}
sort(v.begin(), v.end());
n = v.size();
long long dp[k+1][n+1];
for(int i = 0;i<=n;i++)dp[0][i] = inf;
for(int i = 0;i<=k;i++)dp[i][0] = 0;
for(int j = 1;j<=k;j++) {
for(int i = 1;i<=n;i++) {
long long mx = (v[i-1].first-v[i-1].second);
dp[j][i] = inf;
for(int z = i;z>=1;z--) {
mx = max(mx, (long long)v[i-1].first-v[z-1].second);
long long val = dp[j-1][z-1]+mx*mx;
if(z!=1 and v[z-2].first > v[z-1].second) {
val-=(v[z-2].first-v[z-1].second)*(v[z-2].first-v[z-1].second);
}
dp[j][i] = min(dp[j][i], val);
}
}
}
return dp[k][n];
}
