#include "aliens.h"
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN=1e5+10;
const long long INF=1e15;
struct Interval {
long long l;
long long r;
bool friend operator < (Interval a, Interval b) {
if (a.l==b.l) return a.r>b.r;
return a.l<b.l;
}
};
struct Prava {
long long k;
long long n;
double x;
};
vector <Prava> env[MAXN];
int br[MAXN];
Interval b[MAXN];
vector <Interval> a;
vector <long long> dp[MAXN];
double intersection(long long k1, long long n1, long long k2, long long n2) {
double dk, dn;
dk=k1-k2;
dn=n2-n1;
return dn/dk;
}
void add_prava(int ind, long long k, long long n) {
while (env[ind].size()>1) {
double x=intersection(env[ind].back().k,env[ind].back().n,k,n);
if (x>env[ind].back().x) break;
env[ind].pop_back();
}
if (env[ind].empty()) {
env[ind].push_back({k,n,-INF});
}
double x=intersection(env[ind].back().k,env[ind].back().n,k,n);
env[ind].push_back({k,n,x});
}
void move_br(int ind, double x) {
br[ind]=min(br[ind],(int)env[ind].size()-1);
while (br[ind]<env[ind].size() && env[ind][br[ind]].x<=x) br[ind]++;
br[ind]--;
}
long long take_photos(int n, int m, int k, vector <int> r, vector <int> c) {
for (int i=0;i<n;i++) {
b[i].l=min(r[i],c[i]);
b[i].r=max(r[i],c[i]);
}
sort(b,b+n);
int maxr=b[0].r;
a.push_back({-2,-2});
a.push_back(b[0]);
for (int i=1;i<n;i++) {
if (b[i].r<=maxr) continue;
a.push_back(b[i]);
maxr=b[i].r;
}
n=a.size()-1;
k=min(n,k);
for (int i=0;i<=n;i++) dp[i].resize(k+1);
for (int i=1;i<=n;i++) {
dp[i][0]=INF;
a[i].l--;
}
dp[0][0]=0;
long long dif;
add_prava(0,-2*a[1].l,a[1].l*a[1].l);
for (int i=1;i<=n;i++) {
for (int j=min(i,k);j>=1;j--) {
move_br(j-1,a[i].r);
if (env[j-1].empty()) {
cout << "error\n";
continue;
}
dp[i][j]=env[j-1][br[j-1]].n+env[j-1][br[j-1]].k*a[i].r+a[i].r*a[i].r;
dif=a[i].r-a[i+1].l;
if (dif<0) dif=0;
//cout << i << ' ' << j << ' ' << dp[i][j] << ' ' << dif << ' ' << env[j-1][br[j-1]].n << ' ' << env[j-1][br[j-1]].k*a[i].r << endl;
if (i<n) add_prava(j,-2*a[i+1].l,dp[i][j]+a[i+1].l*a[i+1].l-dif*dif);
}
}
return dp[n][k];
}
