#include<bits/stdc++.h>
#include "aliens.h"
#define int long long
using namespace std;
struct CHT
{
vector<pair<int, int>> line;
vector<int> info;
vector<double> hull;
double intersection(pair<int, int> x, pair<int, int> y)
{
return (double)(x.second - y.second) / (y.first - x.first);
}
void addline(pair<int, int> x, int inf)
{
while(hull.size() > 0 && intersection(x, line[line.size()-1]) <= hull[hull.size()-1]){
hull.pop_back(); line.pop_back(); info.pop_back();
}
if(line.size() > 0) hull.push_back(intersection(line[line.size()-1], x));
line.push_back(x);
info.push_back(inf);
}
pair<int, int> bestval(int x)
{
if(line.size() == 0) return make_pair(1e15, 0);
if(line.size() == 1) return make_pair(line[0].first*x+line[0].second, info[0]);
int place = upper_bound(hull.begin(), hull.end(), x) - hull.begin();
//cout<<line.size()<<" "<<info.size()<<" "<<place<<" "<<info[1]<<endl;
if(place > 0 && line[place].first*x+line[place].second == line[place-1].first*x+line[place-1].second) return make_pair(line[place].first*x+line[place].second, min(info[place], info[place-1]));
else return make_pair(line[place].first*x+line[place].second, info[place]);
}
};
int dp[1000005], cnt[1000005], last[1000005];
inline bool cmp(pair<int, int> x, pair<int, int> y)
{
return x.second < y.second || (x.second == y.second && x.first > y.first);
}
int take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c)
{
//Transform to segments
vector<pair<int, int>> segment;
for(int i = 0; i < n; i++){
if(r[i] <= c[i]) segment.push_back({r[i], c[i]+1});
else segment.push_back({c[i], r[i]+1});
}
//Eliminate unnecessary segments
sort(segment.begin(), segment.end(), cmp);
vector<pair<int, int>> sus;
for(pair<int, int> i : segment){
while(sus.size() > 0 && sus[sus.size()-1].first >= i.first){
sus.pop_back();
}
sus.push_back(i);
}
memset(last, -1, sizeof(last));
for(pair<int, int> i : sus){
last[i.second] = i.first;
//cout<<i.first<<" "<<i.second<<endl;
}
//O(m log n log eps^-1) dp
int le = 0, ri = 1e12, ans = 1e18, lamdaval;
while(le <= ri){
int lambd = (le+ri)/2;
int lastplace = -1;
CHT st;
st.addline({0, 0}, 0);
for(int i = 1; i <= m; i++){
if(last[i] > -1){
pair<int, int> newline;
newline = make_pair(-2*last[i], last[i]*last[i]);
if(last[i] < lastplace) newline.second -= (lastplace - last[i]) * (lastplace - last[i]);
if(lastplace > -1) newline.second += dp[lastplace];
st.addline(newline, cnt[lastplace]);
}
if(last[i] == -1){
dp[i] = dp[i-1]; cnt[i] = cnt[i-1];
}
else{
pair<int, int> sus = st.bestval(i);
dp[i] = i*i + sus.first + lambd;
cnt[i] = sus.second+1;
lastplace = i;
}
//cout<<"A"<<i<<" "<<dp[i]<<" "<<cnt[i]<<endl;
}
if(cnt[m] <= k){
ri = lambd-1;
ans = dp[m];
lamdaval = lambd;
//cout<<lamdaval<<" "<<ans<<" "<<cnt[m]<<endl;
}
else{
le = lambd+1;
}
//cout<<lambd<<" "<<cnt[m]<<endl;
//return 0;
}
return ans - k*lamdaval;
}
/*signed main()
{
cout<<take_photos(5, 6, 4, {0, 1, 2, 3, 4}, {1, 2, 3, 4, 5});
}*/
