#include "aliens.h"
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 0
#define TEST if(test)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e15;
const int MAX_N = 50000;
int N, M, K;
vector<pii> vt;
vector<ll> C;
ll dp[2][MAX_N+1];
bool sf(pii a, pii b){
if(a.first==b.first){
return a.second>b.second;
}
return a.first<b.first;
}
/*struct Lichao{
struct NODE{
int l, r;
ll a, b;
};
ll SZ;
vector<NODE> seg;
void add(){
seg.pb({-1, -1, 0, INFLL});
}
void Init(int x){
SZ = (ll)x;
add();
init(0, 0LL, SZ);
}
void Reset(){
for(int i=0; i<seg.size(); i++){
seg[i].a = 0LL; seg[i].b = INFLL;
}
}
void init(int idx, ll s, ll e){
if(s==e) return;
seg[idx].l = seg.size(); add();
seg[idx].r = seg.size(); add();
init(seg[idx].l ,s, (s+e)/2); init(seg[idx].r, (s+e)/2+1, e);
}
void Update(ll a, ll b){
update(0, 0LL, SZ, a, b);
}
void update(int idx, ll s, ll e, ll x, ll y){
if(s*x+y<=seg[idx].a*s+seg[idx].b && e*x+y<=seg[idx].a*e+seg[idx].b){
seg[idx].a = x;
seg[idx].b = y;
return;
}else if(s*x+y>=seg[idx].a*s+seg[idx].b && e*x+y>=seg[idx].a*e+seg[idx].b){
return;
}
update(seg[idx].l, s, (s+e)/2, x, y);
update(seg[idx].r, (s+e)/2+1, e, x, y);
}
ll Calc(ll x){
return calc(0, 0LL, SZ, x);
}
ll calc(int idx, ll s, ll e, ll k){
if(s==e){
return seg[idx].a * k + seg[idx].b;
}
if(k<=(s+e)/2){
return min(seg[idx].a * k + seg[idx].b, calc(seg[idx].l, s, (s+e)/2, k));
}else{
return min(seg[idx].a * k + seg[idx].b, calc(seg[idx].r, (s+e)/2+1, e, k));
}
}
}Seg;*/
vector<pll> st;
int idx = 0;
void add(ll a, ll b){
while(st.size()>=2){
pll prv = st.back(); st.pop_back();
if((b-prv.second) * (prv.first - st.back().first) >= (a-prv.first) * (prv.second - st.back().second)){
if(idx==st.size()) idx--;
continue;
}else{
st.pb(prv);
break;
}
}
st.pb({a, b});
}
ll calc(ll x){
while(idx+1<st.size()){
if(st[idx+1].first * x + st[idx+1].second < st[idx].first * x + st[idx].second) idx++;
else break;
}
return st[idx].first * x + st[idx].second;
}
void solve(){
dp[1][0] = 0LL;
while(!st.empty()) st.pop_back();
idx = 0;
for(int i=0; i<vt.size(); i++){
//Seg.Update(-2LL * vt[i].first, dp[0][i] - C[i] + (ll)vt[i].first * (ll)vt[i].first);
add(-2LL * vt[i].first, dp[0][i] - C[i] + (ll)vt[i].first * (ll)vt[i].first);
dp[1][i+1] = (ll)vt[i].second * (ll)vt[i].second + calc((ll)vt[i].second);
}
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
N = n; M = m; K = k;
for(int i=0; i<N; i++){
vt.pb({min(r[i], c[i]), max(r[i], c[i]) + 1});
}
sort(vt.begin(), vt.end(), sf);
int mx = -1;
for(int i=0 ;i<N; i++){
if(mx>=vt[i].second){
vt[i].second = INF;
vt[i].first = INF;
}else mx = max(mx, vt[i].second);
}
sort(vt.begin(), vt.end());
while(!vt.empty() && vt.back().first==INF && vt.back().second==INF) vt.pop_back();
for(int i=0; i<=vt.size(); i++){
dp[0][i] = dp[1][i] = INFLL;
}
C.pb(0LL);
for(int i=1; i<vt.size(); i++){
C.pb(max(0LL, (ll)(vt[i-1].second - vt[i].first)) * max(0LL, (ll)(vt[i-1].second - vt[i].first)));
}
dp[0][0] = dp[1][0] = 0LL;
//Seg.Init(M);
while(K--){
solve();
for(int i=0; i<=vt.size(); i++){
//TEST cout<<dp[1][i]<<" ";
dp[0][i] = dp[1][i];
dp[1][i] = INFLL;
}
//TEST cout<<endl;
}
return dp[0][vt.size()];
}
