#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
const ll N = 505;
ll dp[N][N], r[N], c[N], b[N], m[N];
ll intersection(ll i, ll j){
ll A = b[j] - b[i], B = m[i] - m[j], pnt = A / B;
pnt += (A % B != 0);
// cout<<endl;
// cout<<b[j]<<" "<<b[i]<<" "<<m[i]<<" "<<m[j]<<endl;
// cout<<i<<" "<<j<<" "<<A<<" "<<B<<" "<<pnt<<endl;
return pnt;
// return max(A - A + 1 , pnt);
}
long long take_photos(int n, int am, int k, vector<int> x, vector<int> y){
vector<pair<ll, ll>> vc;
for (ll i=0;i<n;i++){
if (x[i] > y[i])
swap(x[i], y[i]);
vc.push_back({x[i] + 1, y[i] + 1});
}
n = 0;
for (ll i=0, mxC = 0;i<vc.size();i++){
if (vc[i].second <= mxC)
continue;
while (r[n] == vc[i].first)
n--;
n++;
r[n] = vc[i].first, c[n] = vc[i].second;
}
for (ll i=0;i<=n;i++){
// cout<<r[i]<<" "<<c[i]<<endl;
m[i] = -2 * r[i + 1];
for (ll j=0;j<=n;j++)
dp[i][j] = 1e9 * (i + j != 0);
}
// cout<<endl;
ll Ans = am * am;
for (ll j=1;j<=k;j++){
vector<ll> v = {0}, st = {0};
for (ll i=1;i<=n;i++){
ll L = 0, R = v.size();
while (L + 1 < R){
ll mid = (L + R) / 2;
if (st[mid] > r[i])
R = mid;
else
L = mid;
}
ll lst = v[L];
// cout<<i<<"_"<<j<<"_"<<lst<<"_"<<dp[lst][j - 1]<<'_';
dp[i][j] = dp[lst][j - 1] + (c[i] - r[lst + 1] + 1) * (c[i] - r[lst + 1] + 1);
if (i + 1 <= n and c[i] >= r[i + 1])
dp[i][j] -= (c[i] - r[i+1] + 1) * (c[i] - r[i+1] + 1);
// cout<<lst<<',';
// cout<<dp[i][j]<<' ';
if (i == n)
continue;
b[i] = dp[i][j - 1] + r[i + 1] * (r[i + 1] - 2) + 1;
while (v.size() > 1 and intersection(v.back(), i) <= st.back())
v.pop_back(), st.pop_back();
st.push_back(intersection(v.back(), i));
v.push_back(i);
// cout<<st.back()<<'\n';
}
// cout<<'\n';
Ans = min(Ans, dp[n][j]);
}
return Ans;
}
