#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
//#define endl '\n'
int n;
map<pair<int,int>,int> aa;
vector<int> xx={0,1,0,-1};
vector<int> yy={1,0,-1,0};
vector<int> adj[2001];
int dist[2001];
int DistanceSum(int nn, int x[], int y[]) {
n=nn;
for(int i=0;i<n;i++){
aa[{x[i],y[i]}]=i;
}
pair<int,pair<int,int>> tt;
for(int i=0;i<n;i++){
for(int j=0;j<4;j++){
if(aa.find({x[i]+xx[j],y[i]+yy[j]})==aa.end()){
continue;
}
adj[i].pb(aa[{x[i]+xx[j],y[i]+yy[j]}]);
}
}
llo ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
dist[j]=-1;
}
dist[i]=0;
priority_queue<pair<int,int>> ac;
ac.push({0,i});
while(ac.size()){
pair<int,int> tt=ac.top();
ac.pop();
tt.a*=(-1);
// cout<<tt.a<<","<<tt.b.a<<","<<tt.b.b<<endl;
for(auto j:adj[tt.b]){
if(dist[j]>tt.a+1 or dist[j]==-1){
dist[j]=tt.a+1;
ac.push({-tt.a-1,j});
}
}
}
for(int j=0;j<n;j++){
ans+=dist[j];
}
// cout<<i<<endl;
}
ans/=2;
ans%=((llo)1e9);
int ans2=ans;
return ans2;
return 0;
}
/*
11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6
*/
/*
g++ -DEVAL -Wall -static -O2 -o aa grader.cpp city.cpp
*/
