#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll nx=5e4+5, kx=105, inf=1e18;
ll dp[kx][nx], area[nx];
stack<int> s;
struct point
{
int x, y;
bool operator< (const point &o) const {
if (x==o.x) return y>o.y;
return x<o.x;
}
} v[nx], p[nx];
struct line
{
ll m, c, p;
line(ll m, ll c, ll p): m(m), c(c), p(p){}
};
struct convexhull
{
deque<line> dq;
ll div(ll a, ll b)
{
if ((a^b)>=0||a%b==0) return a/b;
return a/b-1;
}
void add(ll m, ll c)
{
line nw=line(m, c, inf);
while (dq.size()>=2&&div(nw.c-dq[dq.size()-2].c, dq[dq.size()-2].m-nw.m)<=dq[dq.size()-1].p) dq.pop_back();
if (!dq.empty()) dq.back().p=div(nw.c-dq.back().c,dq.back().m-nw.m);
dq.push_back(nw);
}
ll query(ll x)
{
while (x>dq.front().p) dq.pop_front();
return dq.front().m*x+dq.front().c;
}
} cvh[kx];
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
for (int i=0; i<n; i++) if (r[i]>c[i]) swap(r[i], c[i]);
for (int i=1; i<=n; i++) v[i].x=c[i-1], v[i].y=r[i-1];
sort(v+1, v+n+1);
for (int i=1; i<=n; i++)
{
while (!s.empty()&&v[s.top()].y>=v[i].y) s.pop();
s.push(i);
}
n=s.size();
while (!s.empty()) p[s.size()]=v[s.top()], p[s.size()].x++, p[s.size()].y++, s.pop();
for (int i=2; i<=n; i++) if (p[i-1].x>=p[i].y) area[i]=(p[i-1].x-p[i].y+1)*(p[i-1].x-p[i].y+1);
for (int i=1; i<=n; i++) dp[1][i]=(p[i].x-p[i].y+1)*(p[i].x-p[i].y+1);
for (int i=2; i<=k; i++)
{
for (int j=i; j<=n; j++)
{
cvh[i].add(-2*p[j].y, p[j].y*p[j].y-2*p[j].y+1-area[j]+dp[i-1][j-1]);
dp[i][j]=cvh[i].query(p[j].x)+p[j].x*p[j].x+2*p[j].x;
}
}
/*
for (int i=1; i<=k; i++)
{
for (int j=1; j<=n; j++) cout<<j<<' '<<p[j].x<<' '<<p[j].y<<' '<<dp[i][j]<<'\n';
}*/
k=min(k, n);
return dp[k][n];
}
