#include "aliens.h"
#include<vector>
#include<utility>
#include<algorithm>
#define LL long long
#define MAXN 100005
using namespace std;
class CHT {
vector<pair<pair<LL,LL>, int> > S;
int pt=0;
public:
void reset() {
S.clear();
pt=0;
}
bool bad(LL mq, LL cq, LL num) { //min number of photo
LL m2=S[S.size()-2].first.first, c2=S[S.size()-2].first.second;
LL m1=S.back().first.first, c1=S.back().first.second;
if ((c1-c2)*(m2-mq) != (cq-c2)*(m2-m1)) {
return((c1-c2)*(m2-mq) > (cq-c2)*(m2-m1));
}
return(S.back().second > num);
}
void put(LL m, LL c, LL num) {
while (S.size() > 1 && bad(m,c,num)) {
S.pop_back();
pt=min(pt, (int) S.size()-1);
}
S.push_back({{m,c},num});
}
pair<LL,LL> eval(int l, LL p) {
return(pair<LL,LL> {S[l].first.first*p+S[l].first.second, S[l].second});
}
pair<LL,LL> ask(LL p) { //returns min value & number of photos
while (pt<S.size()-1 && eval(pt, p) > eval(pt+1, p)) {pt++;}
return(eval(pt,p));
}
} CHT;
vector<pair<LL, LL> > Sweep; //r is first l is second
vector<pair<LL,LL> > SS; //sorted stack to get non-dominated points
LL dp[MAXN][2];
pair<LL,LL> slv(LL C) {
CHT.reset();
CHT.put(-2*SS[0].second, SS[0].second*SS[0].second,0);
for (int i=0; i<SS.size(); i++) {
pair<LL,LL> res=CHT.ask(SS[i].first);
dp[i+1][0]=res.first + C + SS[i].first*SS[i].first;
dp[i+1][1]=res.second + 1;
if (i+1<SS.size()) {
LL newm=-2*SS[i+1].second;
LL newc=dp[i+1][0] + SS[i+1].second*SS[i+1].second;
if (SS[i+1].second < SS[i].first) {newc-=(SS[i+1].second - SS[i].first)*(SS[i+1].second - SS[i].first);}
CHT.put(newm, newc, dp[i+1][1]);
}
}
return(pair<LL,LL> {dp[SS.size()][0], dp[SS.size()][1]});
}
LL wqs(LL k) {
LL lo = 0, hi=1LL<<40;
k=min(k, (LL) SS.size());
while (lo + 1 != hi) {
LL mid=(lo+hi)>>1;
if (slv(mid).second > k) {
lo=mid;
} else {
hi=mid;
}
}
return(slv(hi).first - k*hi);
}
LL take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
for (int i=0; i<n; i++) {
Sweep.push_back({max(r[i],c[i])+1, -min(r[i],c[i])});
}
sort(Sweep.begin(), Sweep.end());
for (auto p: Sweep) {
p.second=-p.second;
while (SS.size() && SS.back().second >= p.second) {SS.pop_back();}
SS.push_back(p);
}
return(wqs(k));
}
