二次元平面上に N 匹のきつねがいる． i 番目のきつねのx座標は x_i で，y座標は y_i である．

きつねたちは，特別な力を使って遠く離れた仲間たちと連絡をとりあうことができる． 二匹のきつねの力の強さを p_1, p_2 とし，きつねの間のユークリッド距離を D としたとき， p_1 + p_2 \geq D ならば彼らは連絡をとりあうことができる． ただし，i 番目のきつねと j 番目のきつねのユークリッド距離は \sqrt{ (x_i - x_j) ^ {2} + (y_i - y_j) ^ {2} } である． i 番目のきつねの力の強さは，初め d_i で，コスト c_i を支払うたびに強さを1上昇させることができる．

ここで， N 匹のきつねの間に連絡網 T を作ることを考える． T は N 匹のきつねを頂点とした全域木であり，N - 1 個の辺 (u_1, v_1), …, (u_{N - 1}, v_{N - 1}) からなる．すなわち i = 1, …, N-1 について u_i 番目のきつねと v_i 番目のきつねが辺で結ばれている ． 連絡網 T を作るためには， T 中の任意の辺 (u, v) に対して u番目のきつね と v番目のきつね は連絡をとりあうことができるようにする必要がある． たとえ他のきつねを経由して連絡することができるときも， u 番目のきつね と v 番目のきつね が直接連絡をとりあう状態でなければならない．

必要なコストがなるべく小さくなるようにきつねの力の強さを上昇させたとき， T を作るためのコストはいくつになるか求めなさい．

N
x_1 y_1
…
x_N y_N
d_1 c_1
…
d_N c_N
u_1 v_1
…
u_{N-1} v_{N-1}

入出力例

入力例1

3
0 0
3 0
-3 0
1 100
1 3
1 3
1 2
1 3

出力例1

6

2匹目のきつねと3匹目のきつねの力をそれぞれ1上昇させるのが最善である．

入力例2

3
0 0
3 0
-3 0
1 5
1 3
1 3
1 2
1 3

出力例2

5

1匹目のきつねの力を1上昇させるのが最善である．

入力例3

4
0 0
7 0
-7 0
0 5
2 5
2 1
2 1
2 10
1 2
1 3
1 4

出力例3

9

1匹目のきつねの力を1, 2匹目と3匹目のきつねの力をそれぞれ2上昇させるのが最善である．

入力例4

3
0 0
3 4
6 0
1 1
1 1
1 1
1 2
2 3

出力例4

3

2匹目のきつねの力を3上昇させるのが最善である．