#include<bits/stdc++.h>
#include "aliens.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;

ll calc(ll x,ll y)
{
	return (y-x+1) * (y-x+1);
}
ll calc(array<int,2> t)
{
	return calc(t[0], t[1]);
}

array<int,2> p[MAXN];

ll take_photos(int n, int, int d, vector<int> _r, vector<int> _c)
{
	for(int i=1; i<=n; ++i)
	{
		int x = _r[i-1], y = _c[i-1];
		if(x > y) swap(x, y);
		p[i] = {x, y};
	}
	
	sort(p+1, p+n+1);
	int nn = 0;
	for(int i=1; i<=n; ++i)
	{
		if(nn == 0 || p[i][1] > p[nn][1])
			p[++nn] = p[i];
	}
	n = nn;
	
	ll ans = 0;
	for(int i=1; i<=n; ++i)
		ans += calc(p[i]);
	
	while(n > d)
	{
		int mn = 1;
		ll mnval = linf;
		for(int i=1; i<n; ++i)
		{
			ll cur = calc(p[i][0], p[i+1][1]) - calc(p[i]) - calc(p[i+1]);
			if(cur < mnval)
				mn = i, mnval = cur;
		}
		ans += mnval;
		
		p[mn][1] = p[mn+1][1];
		for(int i=mn+1; i<n; ++i)
			p[i] = p[i+1];
		--n;
	}
	
	return ans;
}