#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ll long long
#define N ((int)50*1001)
#define INF ((ll)1e18)
pair <int,int> a[N],ex[N];
ll dp[2][N];
deque <pair<ll,ll> > lines;
ld barkhord_x(pair <ll,ll> x,pair<ll,ll> y)
{
return (ld)(x.second-y.second)/(y.first-x.first);
}
ll take_photos(int n, int m, int k,vector<int> r,vector<int> c)
{
for(int i=1;i<=n;i++)ex[i]={min(r[i-1],c[i-1])-1,-max(c[i-1],r[i-1])};
sort(ex+1,ex+n+1);
int maxi=-1,n2=0;
for(int i=1;i<=n;i++)
if(-ex[i].second>maxi)
a[++n2]={ex[i].first,-ex[i].second},maxi=-ex[i].second;
n=n2;
dp[0][0]=0;
for(int i=1;i<=n;i++)dp[0][i]=INF;
a[0]={-10,-10};
ll ans=INF;
for(int t=1;t<=k;t++)
{
bool p=(t&1);
lines.clear();
dp[p][0]=INF;
for(int i=1;i<=n;i++)
{
pair <ll,ll> tmp;tmp={-2LL*a[i].first,
dp[!p][i-1]+1LL*a[i].first*a[i].first-1LL*max(0,a[i-1].second-a[i].first)*max(0,a[i-1].second-a[i].first)};
while(lines.size()>1 && barkhord_x(lines.back(),tmp)<=barkhord_x(lines[(int)lines.size()-2],lines.back()))
lines.pop_back();
lines.push_back(tmp);
while(lines.size()>1 && barkhord_x(lines[0],lines[1])<=a[i].second)lines.pop_front();
dp[p][i]=1LL*a[i].second*a[i].second+1LL*a[i].second*lines[0].first+lines[0].second;
}
ans=min(ans,dp[p][n]);
}
return ans;
}
