在二维平面上 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 \leq N \leq 10^3
- |x_i|, |y_i| \leq 10^3
- (x_i, y_i) 是不同的。
- 1 \leq d_i, c_i \leq 10^3
- 1 \leq u_i, v_i \leq N
- T 保证是一棵树。
- 所有输入值都是整数。 第
入出力例
入力例1
3 0 0 3 0 -3 0 1 100 1 3 1 3 1 2 1 3
出力例1
6
第二只狐狸和第三只狐狸的力量最好各增加1。
入力例2
3 0 0 3 0 -3 0 1 5 1 3 1 3 1 2 1 3
出力例2
5
最好将第一只狐狸的力量增加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,第二、第三只狐狸的力量各增加2。
入力例4
3 0 0 3 4 6 0 1 1 1 1 1 1 1 2 2 3
出力例4
3
第二只狐狸的力量最好增加3点。