#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
ll INF=1e12+1;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
ll i, dis, actMa=-1;
vector<ll>ma(m+1,0);
for(i=0; i<n; i++)
{
if(c[i]<r[i])
{
dis=r[i]-c[i];
c[i]=r[i]+dis;
}
ma[r[i]]=max(ma[r[i]],1ll*c[i]);
}
vector<pair<ll,ll>>q;
q.pb({-1,-1});
for(i=0; i<m; i++)
{
if(actMa>=ma[i])
continue;
actMa=ma[i];
q.pb({r[i],ma[i]});
}
vector<vector<ll>>dp(sz(q)+1,vector<ll>(k+1,INF));
ll j, tam, o;
dp[0][0]=0;
for(i=1; i<sz(q); i++)
{
for(j=i-1; j>=0; j--)
{
tam=q[i].se-q[j+1].fr+1;
tam=tam*tam;
for(o=0; o<k; o++)
{
dp[i][o+1]=min(dp[i][o+1],dp[j][o]+tam);
}
}
}
ll ans=INF;
for(i=0; i<=k; i++)
ans=min(ans,dp[sz(q)-1][i]);
return ans;
}
