#include<algorithm>
#include <vector>
#include <stdlib.h>
#include <iostream>
using namespace std;
int DistanceSum(int N, int *X, int *Y) {
vector<vector<int> > d(N, vector<int>(N, N +2));
for (int i=0;i<N;i++){
for (int j=0;j<N;j++){
if (abs(X[i] - X[j]) + abs(Y[i] - Y[j]) <= 1) d[i][j] = abs(X[i] - X[j]) + abs(Y[i] - Y[j]);
}
}
long long M = 1000000000;
long long sum = 0;
for (int k=0;k<N;k++){
for (int i=0;i<N;i++){
for (int j=0;j<N;j++){
if (d[i][k] + d[k][j] < d[i][j]){
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
/*for (int i=0;i<N;i++){
for (int j=i+1;j<N;j++) cout << i << " " << j << " " << d[i][j] << endl;
} */
for (int i=0;i<N;i++){
for (int j=i+1;j<N;j++) sum = (sum + d[i][j]) % M;
}
return sum;
}
