#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
const ll N = 1<<17;
ll dp[N][2], 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 max(pnt, 1LL);
// 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++;
mxC = max(mxC, vc[i].second);
r[n] = vc[i].first, c[n] = vc[i].second;
}
r[n+1] = r[n] + 1;
for (ll i=0;i<=n;i++){
m[i] = -2 * r[i + 1];
for (ll j=0;j<2;j++)
dp[i][j] = 1e16 * (i + j != 0);
}
ll Ans = 1LL * 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] > c[i])
R = mid;
else
L = mid;
}
// ll lst = v[L];
for (int lst=0;lst<i;lst++)
dp[i][1] = min(dp[i][1], dp[lst][0] + (c[i] - r[lst] + 1) * (c[i] - r[lst] + 1));
if (i + 1 <= n and c[i] >= r[i + 1])
dp[i][1] -= (c[i] - r[i+1] + 1) * (c[i] - r[i+1] + 1);
b[i] = dp[i][0] + 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);
}
Ans = min(Ans, dp[n][1]);
for (int i=0;i<=n;i++)
dp[i][0] = dp[i][1], dp[i][1] = 1e16;
}
return Ans;
}
