#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define irep(i,a,b) for(int i = a; i >= b; i--)
typedef long long ll;
typedef long double ld;
//typedef __int128 int128;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<ll,ll> pl;
const int max_n = 507;
const ll INF = 1e12+7;
struct seg{
ll beg;
ll end;
ll a;
ll b;
ll k;
};
pl arr[max_n];
ll odj[max_n]; //stale!
ll dp[max_n][max_n];
vector<pl> points; //do pierwszego sortu!
ll take_photos(int n, int m, int k, vi row, vi col){
//ustawic nowe n!
rep(i,0,n-1){
if(col[i] < row[i]){
//przestawienie na gorna polowe!
int diff = row[i]-col[i];
col[i] += diff;
row[i] -= diff;
}
cout << "i: " << i << " point: " << row[i] << ' ' << col[i] << '\n';
points.pb({row[i],col[i]});
}
sort(points.begin(),points.end());
int akt_ind = 0;
ll max_c = -1;
rep(i,0,n-1){
if(points[i].nd <= max_c) continue; //jest dalej mniejsze h!
if(i != n-1 && points[i+1].st == points[i].st) continue; //ten sam rząd
arr[++akt_ind] = points[i];
max_c = points[i].nd;
}
//policzyc odj!
rep(i,2,akt_ind){
if(arr[i].st > arr[i-1].nd) continue;
ll val = arr[i-1].nd-arr[i].st+1;
odj[i] = val*val;
}
rep(i,1,akt_ind){
cout << "i: " << i << " arr: " << arr[i].st << ' ' << arr[i].nd << " odj: " << odj[i] << '\n';
}
k = min(k,akt_ind); //wazne, zeby za duzo prostokatow nie robic!!!
rep(i,0,n) rep(j,0,n) dp[i][j] = INF;
dp[0][0] = 0;
rep(i,1,n)
rep(j,1,k)
rep(prev,0,i-1){
ll val = (arr[i].nd-arr[prev].st+1)*(arr[i].nd-arr[prev].st+1);
dp[i][j] = max(dp[i][j],dp[prev][j-1]+val-odj[prev]);
}
return dp[n][k];
}
