#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define INF 1e18
#define SQ(x) ((x)*(x))
int qtd[N]; // Quantidade de retangulos usados pela PD
long long dp[N]; // PD
// Definindo a estrutura Ponto
#define X first
#define Y second
typedef pair<long long, long long> Ponto;
vector<Ponto> pts;
int solve(int n, long long C)
{
// Casos bases da PD
dp[0] = 0; qtd[0] = 0;
// Execucao da PD
for (int i = 1; i <= n; i++)
{
dp[i] = INF;
for (int w = 1; w <= i; w++)
{
long long aux = SQ(pts[i].Y - pts[w].X + 1ll) + dp[w - 1] - SQ(max(0ll, pts[w - 1].Y - pts[w].X + 1ll)) + C;
if (dp[i] > aux)
{
dp[i] = aux;
qtd[i] = 1 + qtd[w - 1]; // Numero de quadrados usados
}
}
}
return qtd[n]; // Retorna quantos quadrados foram usados
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
// Ordenamos os pontos pela linha (desempate pela coluna)
set<Ponto> pontos;
for (int i = 0; i < n; i++)
if (r[i] <= c[i])
// Ponto acima ou dentro da diagonal principal
pontos.insert({r[i], c[i]});
else
// Ponto abaixo da diagonal principal, entao espelhamos ele
pontos.insert({c[i], r[i]});
// Vector para armazenar os pontos que importam
pts.push_back({-INF, -INF});
// Selecionando apenas os pontos que realmente importam
for (auto p : pontos)
{
Ponto ultimo = pts.back();
if (ultimo.X == p.X) // Pontos na mesma linha
pts[pts.size() - 1] = p;
else if (ultimo.Y < p.Y) // Pontos em linha diferentes
pts.push_back(p);
}
n = pts.size() - 1; // Atualizando o valor de n
k = min(k, n); // Atualizando o valor de k
// Busca binária no custo C
long long ini = 0, fim = (long long) m * m;
while (fim > ini)
{
long long mei = (ini + fim) / 2ll;
if (solve(n, mei) <= k)
fim = mei;
else
ini = mei + 1;
}
solve(n, ini);
return dp[n] - k * ini;
}
