#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll INF = 1000000000000000000LL;
const int N = 1000000;
struct line{
ll k, n;
ll eval(ll x){ return k*x + n; }
ld intersect(line g){
return 1.0*(n - g.n)/(g.k - k);
}
} seg[4*N+5];
ll dp[N+5];
ll presek(pair <ll, ll> a, pair <ll, ll> b){
ll h = max(0LL, a.second - b.first + 1);
return h*h;
}
void dodaj(deque <line> &q, line k){
while(q.size() > 1){
line g = q.back();
q.pop_back();
ld x1 = q.back().intersect(g);
ld x2 = g.intersect(k);
if(x1 < x2){
q.push_back(g);
break;
}
}
q.push_back(k);
}
ll query(deque <line> &q, ll x){
while(q.size() > 1 && q[0].eval(x) >= q[1].eval(x)) q.pop_front();
return q.front().eval(x);
}
long long take_photos(int n, int m, int k, std::vector<int> _r, std::vector<int> _c) {
vector <pair <int, int>> points;
for(int i=0; i<n; i++){
if(_r[i] > _c[i]) swap(_r[i], _c[i]);
points.push_back({_r[i] + 1, _c[i] + 1});
}
sort(points.begin(), points.end(), [](pair <int, int> a, pair <int, int> b){ if(a.second == b.second) return a.first < b.first; return a.second > b.second; });
vector <pair <ll, ll>> vec;
for(auto c : points){
if(vec.empty() || c.first < vec.back().first) vec.push_back(c);
}
reverse(vec.begin(), vec.end());
n = vec.size();
ll res = INF;
for(int turns=1; turns<=k; turns++){
deque <line> q;
if(turns == 1) dodaj(q, {-2*(vec[0].first - 1), vec[0].first*vec[0].first - 2*vec[0].first});
for(int i=0; i<n; i++){
ll g = dp[i];
dp[i] = 1 + vec[i].second*vec[i].second + query(q, vec[i].second);
if(i != n-1 && turns != 1) dodaj(q, {-2*(vec[i+1].first - 1), vec[i+1].first*vec[i+1].first - 2*vec[i+1].first - presek(vec[i], vec[i+1]) + g});
}
res = min(res, dp[n-1]);
while(!q.empty()) q.pop_back();
}
return res;
}
