题目背景：
一座城市，往往会被人们划分为几个区域。例如住宅区、商业区、工业区等等。B市就被分为了两个区域——城市中心和城市郊区。这两个区域的中间是一条围绕B市的环路，环路之内便是B市中心。

题目描述：
B市可以看作是一个由N个点，N条道路的构成的无向连通图，图中唯一的环即为绕城的环路，其他部分则隶属城市郊区。
alan想在B市开店，店铺只能开在图中的点上，每个点都有一个人流量P_i，在点i处开店所能获得的利润等于该点的人流量P_i×K，但任意一条道路所连接的两个点不能同时开店，开店的总数目没有限制。
alan想赚取尽量多的利润，请问他应该在哪些地方开店？你只需要求出最大的利润值。

第一行一个整数N，代表城市的点的数目。城市中的点由0~N-1编号。
第二行N个正整数，第i个数代表点i-1的人流量Pi-1。
接下来N行，每行两个整数x,y，表示x与y之间有一条双向道路。
最后一行为一个实数K。

一个实数，即开店所能获得的最大利润。保留一位小数。

样例解释：
选择在2号和3号节点开店，可获得最大利润(1+5)×2=12.0。

数据范围：
对于20%的数据:N<=100。
对于50%的数据:N<=2000。
对于100%的数据:N<=100000,P_i<=10000, K<=10000。
对于所有的数据，保证图连通，图中有且仅有一个环且没有重边。