U163163 海贼王（pirate）

gx 是我们的红太阳！！

总所周知，动漫《海贼王》里有许多大海贼团，他们每个人都在海上有一定的 领地。今天世界政府想要评估一下当下海贼的势力值。为了简化计算，做如下设定， 每个海贼团作为一个节点，单个海贼团有其威望值 $a_i$，当其作为整个海贼组织的领袖——海贼王时，对于海上的海贼势力值计算为: $\sum^{n}_{i=1}{dist(i,v)*a_i}$ 其中: $v$表示当选海贼王的海贼团; $dist(i,v)$ 表示 $v$ 到 $i$ 的距离.

第一行输入一个数

输出当下海贼最大势力值。

 上图为输入样例对应的图，当编号为3的海贼团当上海贼王时，其的势力值最大。 $2*9+1*4+0*1+3*7+3*10+4*1+4*6+4*5=18+4+0+21+30+4+24+20=121。 $ [数据范围与提示] 对于 50% 数据 ， 1 $\leq$ n $\leq$10000, 1 $\leq$ $a_i$ $\leq$ 5 $\times$ $10^5$. 对于 100% 数据， 1 $\leq$ n $\leq$ $2 \times 10^5$, 1 $\leq$ $a_i$ $\leq$ 5 $\times$ $10^5$. 要开 long long！