#include "aliens.h"
#include <bits/stdc++.h>
using namespace std ;
typedef pair<int,int> pii ;
typedef long long ll ;
const int M = 1e6+2 ;
const int N = 6e4 ;
const ll inf = 1e15 ;
int mxCoor[ M ] ;
vector <pii> points ;
int sz ;
ll dp [N][3];
int ac ;
void solve ( int l, int r, int optl, int optr ) {
if ( l > r ) return ;
int mid = (l+r)>>1 ;
dp[mid][ac%2] = inf ;
int optimal = 0 ;
for ( int k = optl ; k < min (optr+1, mid) ; ++k ) {
ll inters = points[k].second - points[k+1].first + 1;
if ( inters < 0 ) inters = 0 ;
inters *= inters ;
// cout << k << " to " << k+1 << ' ' << inters << ' ' << points[k].second << ' ' << points[k+1].first << '\n' ;
ll cost = points[mid].second - points[k+1].first + 1;
cost *= cost;
cost -= inters ;
// cout << dp[k][(ac-1)%2] << ' ' << cost << ' ' << dp[mid][ac%2] << endl ;
if ( dp[k][(ac-1)%2] + cost < dp[mid][ac%2] ) {
dp[mid][ac%2] = dp[k][(ac-1)%2] + cost ;
optimal = k ;
}
}
solve ( l, mid-1, optl, optimal ) ;
solve ( mid+1, r, optimal, optr ) ;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
memset ( mxCoor, -1, sizeof mxCoor ) ;
for ( int i = 0 ; i < n ; ++i ) {
if ( c[i] >= r[i] ) mxCoor [r[i]] = max ( mxCoor [r[i]], c[i] ) ;
else mxCoor [c[i]] = max ( mxCoor [c[i]], r[i] ) ;
}
int mx = -1 ;
points.push_back({-1,-1}) ;
for ( int i = 0 ; i < m ; ++i ) {
if ( mxCoor[i] <= mx ) continue ;
mx = mxCoor[i] ;
points.push_back({i,mx}) ;
}
sz = points.size() ;
for ( int i = 1 ; i < sz ; ++i ) dp[i][0] = inf ;
for ( int i = 1 ; i <= k ; ++i ) {
ac = i ;
solve ( 1, sz-1, 0, sz-1 ) ;
}
return dp[sz-1][k%2];
}
