9288 - 小李开店

通过次数

3

提交次数

3

时间限制 : 1 秒
内存限制 : 512 MB

昆明市,被划分为五华区、呈贡区、官渡区、盘龙区等的好几个区域,在各区之间有着多条环路,环路之内便是昆明市市中心。
假如整个城市可以看做一个n个点,n条边的单圈图(保证图连通),唯一的环便是绕城的环路。保证环上任意两点有且只有2条简单路径互通。图中的其它部分皆隶属昆明市郊区。
现在,有一位刚毕业的大学生小李 想在昆明市开店,但是任意一条边的2个点不能同时开店,每个点都有一定的人流量,第i个点的人流量是pi,在该点开店的利润就等于pi×k,其中k是一个常数。
小李想尽量多的赚取利润,请问他应该在哪些地方开店?

输入

第一行一个整数n,代表城市中点的个数。
城市中的n个点由1∼n编号。
第二行有n个整数,第i个整数表示第i个点的人流量pi。
接下来n 行,每行有两个整数u,v,代表存在一条连接u和v 的道路。
最后一行有一个实数,代表常数k。

输出

输出一行一个实数代表答案,结果保留一位小数。

样例

输入

4
2 2 1 4
1 2
1 3
3 4
3 2
1

输出

6.0

输入

10
6 5 8 9 2 9 3 1 4 10
1 2
2 3
1 4
4 5
2 6
4 7
3 8
2 9
2 10
10 3
2

输出

70.0

输入

8
7 5 7 4 7 5 8 1
1 2
1 3
2 4
2 5
4 6
5 7
2 8
4 2
5

输出

125.0

提示

【数据范围】