#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define SQ(x) ((long long)(x)*(x))
struct Line {
int m;
long long c;
int u;
pair<long long,int> eval(int x) {
return make_pair((long long)m*x + c, u);
}
};
struct ConvexHull {
deque<Line> dq;
long double intersect(Line a, Line b) {
return (long double)(a.c-b.c)/(b.m-a.m);
}
void add(int m, long long c, int u) {
Line l = {m,c,u};
while (!dq.empty() && dq.front().m >= m) dq.pop_front();
while (SZ(dq) > 1 && intersect(l,dq[0]) >= intersect(dq[0],dq[1])) dq.pop_front();
if (dq.empty() || c < dq.front().c) dq.push_front(l);
}
pair<long long,int> query(int x) {
while (SZ(dq) > 1 && intersect(dq[SZ(dq)-2],dq.back()) >= x) dq.pop_back();
return dq.back().eval(x);
}
void dbg() {
for (auto& x : dq) cout << x.m << " " << x.c << " :: " << x.u << endl;
cout << endl;
}
};
pair<long long,int> solve(int n, int m, vector<array<int,2>>& p, long long lcost) {
pair<long long,int> dp[n+1];
dp[n] = make_pair(0,0);
stack<int> stk; stk.push(n);
ConvexHull ch;
RFOR(i,n-1,0){
while (!stk.empty() && p[stk.top()][1] <= p[i][1]) stk.pop();
long long overlap = (!stk.empty() && p[stk.top()][0] <= p[i][1] ? SQ(p[i][1]+1-p[stk.top()][0]) : 0);
ch.add(-2*(p[i][1]+1), dp[stk.top()].first + SQ(p[i][1]+1) - overlap, dp[stk.top()].second);
dp[i] = ch.query(p[i][0]);
dp[i].first += SQ(p[i][0]) + lcost;
dp[i].second += 1;
stk.push(i);
//dp[j+1].first + SQ(p[j][1]+1) - 2*(p[j][1]+1)*p[i][0] + SQ(p[i][0])
// - SQ(p[j][1]+1-p[j+1][0]) if overlap
//cout << overlap << " " << ch.query(p[i][0]).first << " " << SQ(p[i][0]) << endl;
//cout << "QUERY " << p[i][0] << endl;
//cout << "dp " << i << " :: " << dp[i].first << ' ' << dp[i].second << endl;
//ch.dbg();
}
return dp[0];
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vector<array<int,2>> p;
FOR(i,0,n-1){
if (r[i] > c[i]) p.push_back(array<int,2>{c[i],r[i]});
else p.push_back(array<int,2>{r[i],c[i]});
}
sort(p.begin(),p.end());
p.push_back(array<int,2>{1000005,1000005});
//for(auto&x:p){
// cout<<x[0]<<' '<<x[1]<<endl;
//}
long long lo = 0, hi = 1e12+10;
while (hi-lo > 1) {
long long mid = (lo+hi)/2;
auto res = solve(n,m,p,mid);
//cout << mid << " :: " << res.first << " " << res.second << endl;
if (res.second <= k) hi = mid;
else lo = mid;
}
//cout << hi << endl;
auto ans = solve(n,m,p,hi);
//cout << ans.first << " " << ans.second << endl;
return ans.first - ans.second * hi;
}
