#include <bits/stdc++.h>
#include "aliens.h"
#define X first
#define Y second
#define MAXK 510
#define MAXN 50010
#define INF 1000000000000000000LL
using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
class ConvexHullTrick
{
public:
bool check(lli a, lli b, lli c, lli d)
{
if(a/b != c/d) return a/b >= c/d;
a %= b; c %= d;
if(a == 0 && c == 0) return true;
if(a == 0 && c != 0) return false;
if(c == 0) return true;//verificar essas condições
return check(d , c , b , a);
}
void add(lli a, lli b)
{
while( sz > 2 && check(B[sz - 1] - B[sz] , A[sz] - A[sz - 1] , B[sz - 1] - b , a - A[sz - 1]))
{
A.pop_back();
B.pop_back();
sz--;
}
A.push_back( a );
B.push_back( b );//sz = quantas retas tem
sz++;
}
double iniLine(int i)
{
if(i == 0) return -INF;
return (double (B[i - 1] - B[i]))/(A[i] - A[i - 1]);
}
lli query(lli x)
{
if(opt >= sz) opt = sz - 1;
while(opt < sz - 1 && A[opt]*x + B[opt] >= A[opt + 1]*x + B[opt + 1])
opt++;
return A[opt]*x + B[opt];
}
void clear()
{
A.clear();
B.clear();
sz = 0;
opt = 0;
}
private:
int sz;
int opt;
vector<lli> A, B;
};
lli N, M, K;
lli dp[MAXN][MAXK];
vector<pii> points;
ConvexHullTrick CHT;
void convertPoints()
{
for(int g = 1 ; g <= N ; g++)
{
points[g].X++;
points[g].Y = M - points[g].Y;
}
}
void reflectPoints()
{
for(int g = 1 ; g <= N ; g++)
{
if(points[g].X + points[g].Y < M + 1)
{
pii aux;
aux.X = M + 1 - points[g].Y;
aux.Y = M + 1 - points[g].X;
points[g] = aux;
}
}
}
void makeParetto()
{
sort(points.begin() , points.end());
vector<pii> paretto;
paretto.push_back({-INF , INF});
paretto.push_back( points[1] );
for(int g = 2 ; g <= N ; g++)
{
while( points[g].Y >= paretto.back().Y )
paretto.pop_back();
paretto.push_back( points[g] );
}
points.clear();
for(int g = 0 ; g < paretto.size() ; g++)
points.push_back( paretto[g] );
}
void printPoints()
{
for(int g = 1 ; g < points.size() ; g++)
printf("(%lld ; %lld) ",points[g].X,points[g].Y);
printf("\n");
}
long long int take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
N = n; M = m; K = k;
points.push_back({-1 , -1});
for(int g = 0 ; g < n ; g++)
points.push_back({c[g] , r[g]});
convertPoints();
//printPoints();
reflectPoints();
//printPoints();
makeParetto();
//printPoints();
dp[0][0] = 0;
for(int g = 1 ; g <= n ; g++)
dp[g][0] = INF;
for(int l = 1 ; l <= k ; l++)
{
CHT.clear();
CHT.add( points[1].Y , - 2*M*points[1].Y + (points[1].Y * points[1].Y));
//printf("BASE %lld %lld\n",2*points[1].Y,points[1].Y*points[1].Y);
for(int i = 1 ; i < points.size() ; i++)
{
lli out = (points[i].X * points[i].X);
out -= 2*M*points[i].X;
out += M*M;
dp[i][l] = CHT.query( 2*points[i].X ) + out;
//printf("query = %lld\n",CHT.query(2*points[i].X));
//printf("dp(%d,%d) = %lld\n",i,l,dp[i][l]);
if(i == points.size() - 1) continue;
CHT.add( points[i + 1].Y , dp[i][l - 1] - 2*M*points[i + 1].Y + (points[i + 1].Y * points[i + 1].Y));
}
}
return dp[points.size() - 1][K];
}
/*int main()
{
int nn, mm, kk;
int n1, n2;
scanf("%d %d %d",&nn,&mm,&kk);
vector<int> xx, yy;
for(int g = 0 ; g < nn ; g++)
{
scanf("%d %d",&n1,&n2);
xx.push_back(n1);
yy.push_back(n2);
}
printf("%lld\n",take_photos(nn , mm , kk , xx , yy));
}*/
