#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#pragma once
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Line {
mutable ll k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
static const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) return x->p = inf, 0;
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m) {
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
ll query(ll x) {
assert(!empty());
auto l = *lower_bound(x);
return l.k * x + l.m;
}
};
bool cmp(pair<long long,long long> a,pair<long long,long long> b)
{
if(a.first==b.first)
return a.second>b.second;
return a.first<b.first;
}
bool inters(pair<int,int> a,pair<int,int> b)
{
if(a.first<=b.first && a.second>=b.second)
return true;
return false;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
if(n<=50 && m<=100 && k==n) //First Subtask
{
int sol = 0;
vector<vector<int> > matrix;
matrix.resize(m);
for(int i = 0;i<m;i++)
matrix[i].resize(m);
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
matrix[i][j] = 0;
for(int i = 0;i<n;i++)
{
if(matrix[r[i]][c[i]]) continue;
int m = min(r[i],c[i]);
int M = max(r[i],c[i]);
for(int j = m;j<=M;j++)
for(int t = m;t<=M;t++)
matrix[j][t] = 1;
}
for(int i = 0;i<m;i++)
for(int j=0;j<m;j++)
sol+=matrix[i][j];
return sol;
}
bool flag = true;
for(int i = 0;i<n;i++)
if(r[i]!=c[i])
{
flag = false;
break;
}
if(n<=500 && m<=1000 && flag)
{
vector<pair<int,int> > obj;
for(int i = 0;i<n;i++)
obj.emplace_back(r[i],c[i]);
sort(obj.begin(),obj.end());
vector<vector<int> > dp;
dp.resize(n+1);
for(int i=0;i<=n;i++)
{
dp[i].resize(k+1);
for(int j=0;j<=k;j++)
dp[i][j] = 1000000000;
}
dp[0][0] = 0;
for(int i = 0;i<n;i++)
{
for(int j = 0;j<=i;j++) {
for (int t = 1; t <= k; t++) {
int area = (obj[i].first - obj[j].first + 1) * (obj[i].second - obj[j].second + 1);
dp[i+1][t] = min(dp[i+1][t], dp[j][t-1] + area);
}
}
}
int sol = INT_MAX;
for(int j=1;j<=k;j++)
sol=min(sol,dp[n][j]);
return sol;
}
else
if(n<=500 && m<=1000)
{
vector<pair<int,int> > obj;
vector<pair<int,int> > aux;
for(int i = 0;i<n;i++)
aux.emplace_back(min(r[i],c[i]),max(r[i],c[i]));
sort(aux.begin(),aux.end(),cmp);
obj.emplace_back(-1,-1);
for(auto it:aux)
{
if(!inters(obj.back(),it))
obj.push_back(it);
}
n = obj.size();
vector<vector<int> > dp;
dp.resize(n+1);
for(int i=0;i<=n;i++)
{
dp[i].resize(k+1);
for(int j=0;j<=k;j++)
dp[i][j] = 1000000000;
}
dp[0][0] = 0;
for(int i = 1;i<n;i++)
{
for(int j = 1;j<=i;j++)
{
for(int t=1;t<=k;t++)
{
dp[i][t] = min(dp[i][t],dp[j-1][t-1] + (obj[i].second-obj[j].first+1)*(obj[i].second-obj[j].first+1) - max(0,obj[j-1].second-obj[j].first+1)*max(0,obj[j-1].second-obj[j].first+1));
}
}
}
int sol = INT_MAX;
for(int j=1;j<=k;j++)
sol=min(sol,dp[n-1][j]);
return sol;
}
else
if(n<=50000 && m<=1000000)
{
vector<pair<long long,long long> > obj;
vector<pair<long long,long long> > aux;
for(int i = 0;i<n;i++)
aux.emplace_back(1LL*min(r[i],c[i]),1LL*max(r[i],c[i]));
sort(aux.begin(),aux.end(),cmp);
obj.emplace_back(-1,-1);
for(auto it:aux)
{
if(!inters(obj.back(),it))
obj.push_back(it);
}
n = obj.size();
vector<vector<long long> > dp;
dp.resize(n+1);
for(int i=0;i<=n;i++)
{
dp[i].resize(k+1);
for(int j=0;j<=k;j++)
dp[i][j] = (1LL*m)*(1LL*m);
}
dp[0][0] = 0;
LineContainer lc;
lc.add(2*obj[1].first,-dp[0][0]-obj[1].first*obj[1].first);
for(int t=1;t<=k;t++)
{
for(int i=1;i<n;i++)
{
if(!lc.empty()) {
long long zi = obj[i].second + 1;
long long res = -lc.query(zi);
dp[i][t] = min(dp[i][t], res + zi * zi);
}
if(i!=(n-1) && dp[i][t-1]!=(1LL*m)*(1LL*m)) {
long long intersection = max(0LL,obj[i].second-obj[i+1].first+1LL)*max(0LL,obj[i].second-obj[i+1].first+1LL);
lc.add(2 * obj[i + 1].first, -dp[i][t - 1] - obj[i + 1].first * obj[i + 1].first + intersection);
}
}
lc.clear();
}
long long sol = (1LL*m)*(1LL*m);
for(int j=1;j<=k;j++)
sol=min(sol,dp[n-1][j]);
return sol;
}
return 0;
}
