#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
#define pb push_back
#define all(x) x.begin(), x.end()
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
using namespace std;
const int MOD = 1000000000, N = 3000;
int delta[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool estVille[N][N], vue[N][N];
int dist[N][N];
long long inv(long long a, long long b){
return 1<a ? b - inv(b%a,a)*b/a : 1;
}
int DistanceSum(int nVilles, int *X, int *Y) {
vector<int> x, y;
for (int iVille = 0; iVille < nVilles; ++iVille){
x.pb(X[iVille]);
y.pb(Y[iVille]);
}
long long SUM = 0;
sort(all(x)); sort(all(y));
long long sumPg = 0, sumPp = 0;
for (int e : x){
sumPg = (sumPg + e);
}
sumPg = (sumPg - x[0]);
for (int ind = 0; ind < nVilles; ++ind){
int add = (ind * x[ind] - sumPp);
add = (add + sumPg - (nVilles - 1 - ind) * x[ind]);
SUM = (SUM + add);
if (ind != nVilles - 1){
sumPg = (sumPg - x[ind + 1]);
}
sumPp = (sumPp + x[ind]);
}
//cout << "sum " << SUM << endl;
sumPg = 0, sumPp = 0;
for (int e :y)
sumPg = (sumPg + e);
sumPg = (sumPg - y[0])%MOD;
for (int ind = 0; ind < nVilles; ++ind){
int add = (ind * y[ind] - sumPp);
// cout << "add" << add << endl;
add = (add + sumPg - (nVilles - 1 - ind) * y[ind]);
// cout << "add " << add << endl;
SUM = (SUM + add);
if (ind != nVilles - 1){
sumPg = (sumPg - y[ind + 1]);
}
sumPp = (sumPp + y[ind]);
}
//cout << "SUM " << SUM << endl;
return (int)(SUM/2);
}
