#include <bits/stdc++.h>
#include "aliens.h"
#define ff first
#define ss second
using namespace std;
long long take_photos(int N, int R, int K, vector<int> x, vector<int> y) {
vector< pair<int,int> > Iall(N);
for(int i =0; i < N; i++) {
Iall[i].ff =min(x[i],y[i]);
Iall[i].ss =max(x[i],y[i])+1;}
sort(begin(Iall),end(Iall));
vector< pair<int,int> > I;
int rp =-1;
for(int i =0; i < N; i++) {
if(i < N-1 && Iall[i].ff == Iall[i+1].ff) continue;
if(Iall[i].ss <= rp) continue;
I.push_back(Iall[i]);
rp =Iall[i].ss;}
N =I.size();
K =min(K,N);
long long ans =1e18;
long long costA =-1, costB =1e13;
while(costB-costA > 1) {
long long cost =(costA+costB)/2;
vector<long long> A(N+1,1e18);
vector<int> curK(N+1,0);
A[0] =0;
vector< pair<long long,int> > q;
int a =-1;
for(int i =0; i < N; i++) {
long long x =A[i]+1LL*I[i].ff*I[i].ff, y =2*I[i].ff;
while(q.size() >= 2) {
long long x2 =q.back().ff, y2 =2*I[q.back().ss].ff;
long long x1 =q[q.size()-2].ff, y1 =2*I[q[q.size()-2].ss].ff;
if(1.0*(x2-x1)/(y2-y1) > 1.0*(x-x2)/(y-y2)) q.pop_back();
else break;}
a =min(a,(int)q.size()-1);
q.push_back(make_pair(x,i));
if(a == -1) a++;
while(a < (int)q.size()-1) {
if(q[a].ff-2LL*I[q[a].ss].ff*I[i].ss >= q[a+1].ff-2LL*I[q[a+1].ss].ff*I[i].ss) a++;
else break;}
A[i+1] =q[a].ff-2LL*I[q[a].ss].ff*I[i].ss+1LL*I[i].ss*I[i].ss+cost;
curK[i+1] =curK[q[a].ss]+1;
if(i < N-1 && I[i+1].ff < I[i].ss)
A[i+1] -=1LL*(I[i].ss-I[i+1].ff)*(I[i].ss-I[i+1].ff);
}
if(curK[N] >= K) {
costA =cost;
ans =A[N]-K*cost;}
else costB =cost;}
return ans;}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlICJhbGllbnMuaCIKI2RlZmluZSBmZiBmaXJzdAojZGVmaW5lIHNzIHNlY29uZAp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKbG9uZyBsb25nIHRha2VfcGhvdG9zKGludCBOLCBpbnQgUiwgaW50IEssIHZlY3RvcjxpbnQ+IHgsIHZlY3RvcjxpbnQ+IHkpIHsKCXZlY3RvcjwgcGFpcjxpbnQsaW50PiA+IElhbGwoTik7Cglmb3IoaW50IGkgPTA7IGkgPCBOOyBpKyspIHsKCQlJYWxsW2ldLmZmID1taW4oeFtpXSx5W2ldKTsKCQlJYWxsW2ldLnNzID1tYXgoeFtpXSx5W2ldKSsxO30KCXNvcnQoYmVnaW4oSWFsbCksZW5kKElhbGwpKTsKCXZlY3RvcjwgcGFpcjxpbnQsaW50PiA+IEk7CglpbnQgcnAgPS0xOwoJZm9yKGludCBpID0wOyBpIDwgTjsgaSsrKSB7CgkJaWYoaSA8IE4tMSAmJiBJYWxsW2ldLmZmID09IElhbGxbaSsxXS5mZikgY29udGludWU7CgkJaWYoSWFsbFtpXS5zcyA8PSBycCkgY29udGludWU7CgkJSS5wdXNoX2JhY2soSWFsbFtpXSk7CgkJcnAgPUlhbGxbaV0uc3M7fQoJTiA9SS5zaXplKCk7CglLID1taW4oSyxOKTsKCglsb25nIGxvbmcgYW5zID0xZTE4OwoJbG9uZyBsb25nIGNvc3RBID0tMSwgY29zdEIgPTFlMTM7Cgl3aGlsZShjb3N0Qi1jb3N0QSA+IDEpIHsKCQlsb25nIGxvbmcgY29zdCA9KGNvc3RBK2Nvc3RCKS8yOwoJCXZlY3Rvcjxsb25nIGxvbmc+IEEoTisxLDFlMTgpOwoJCXZlY3RvcjxpbnQ+IGN1cksoTisxLDApOwoJCUFbMF0gPTA7CgkJdmVjdG9yPCBwYWlyPGxvbmcgbG9uZyxpbnQ+ID4gcTsKCQlpbnQgYSA9LTE7CgkJZm9yKGludCBpID0wOyBpIDwgTjsgaSsrKSB7CgkJCWxvbmcgbG9uZyB4ID1BW2ldKzFMTCpJW2ldLmZmKklbaV0uZmYsIHkgPTIqSVtpXS5mZjsKCQkJd2hpbGUocS5zaXplKCkgPj0gMikgewoJCQkJbG9uZyBsb25nIHgyID1xLmJhY2soKS5mZiwgeTIgPTIqSVtxLmJhY2soKS5zc10uZmY7CgkJCQlsb25nIGxvbmcgeDEgPXFbcS5zaXplKCktMl0uZmYsIHkxID0yKklbcVtxLnNpemUoKS0yXS5zc10uZmY7CgkJCQlpZigxLjAqKHgyLXgxKS8oeTIteTEpID4gMS4wKih4LXgyKS8oeS15MikpIHEucG9wX2JhY2soKTsKCQkJCWVsc2UgYnJlYWs7fQoJCQlhID1taW4oYSwoaW50KXEuc2l6ZSgpLTEpOwoJCQlxLnB1c2hfYmFjayhtYWtlX3BhaXIoeCxpKSk7CgkJCWlmKGEgPT0gLTEpIGErKzsKCQkJd2hpbGUoYSA8IChpbnQpcS5zaXplKCktMSkgewoJCQkJaWYocVthXS5mZi0yTEwqSVtxW2FdLnNzXS5mZipJW2ldLnNzID49IHFbYSsxXS5mZi0yTEwqSVtxW2ErMV0uc3NdLmZmKklbaV0uc3MpIGErKzsKCQkJCWVsc2UgYnJlYWs7fQoJCQlBW2krMV0gPXFbYV0uZmYtMkxMKklbcVthXS5zc10uZmYqSVtpXS5zcysxTEwqSVtpXS5zcypJW2ldLnNzK2Nvc3Q7CgkJCWN1cktbaSsxXSA9Y3VyS1txW2FdLnNzXSsxOwoJCQlpZihpIDwgTi0xICYmIElbaSsxXS5mZiA8IElbaV0uc3MpIAoJCQkJQVtpKzFdIC09MUxMKihJW2ldLnNzLUlbaSsxXS5mZikqKElbaV0uc3MtSVtpKzFdLmZmKTsKCQkJfQoJCWlmKGN1cktbTl0gPj0gSykgewoJCQljb3N0QSA9Y29zdDsKCQkJYW5zID1BW05dLUsqY29zdDt9CgkJZWxzZSBjb3N0QiA9Y29zdDt9CgkKCXJldHVybiBhbnM7fQ==