城市环路

题目背景

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

题目描述

整个城市可以看做一个N个点,N条边的单圈图(保证图连通),唯一的环便是绕城的环路。保证环上任意两点有且只有2条路径互通。图中的其它部分皆隶属城市郊区。 现在,有一位名叫Jim的同学想在B市开店,但是任意一条边的2个点不能同时开店,每个点都有一定的人流量Pi,在该点开店的利润就等于该店的人流量Pi×K(K≤10000),K的值将给出。 Jim想尽量多的赚取利润,请问他应该在哪些地方开店?

输入输出格式

输入格式


第一行一个整数N 代表城市中点的个数。城市中的N个点由0~N-1编号。 第二行N个正整数,表示每个点的人流量Pi(Pi≤10000)。 下面N行,每行2个整数A,B,表示A,B建有一条双向路。 最后一行一个实数K。

输出格式


一个实数M,(保留1位小数),代表开店的最大利润。

输入输出样例

输入样例 #1

4
1 2 1 5
0 1
0 2
1 2
1 3
2

输出样例 #1

12.0

说明

【数据范围】 对于20%的数据,N≤100. 对于另外20%的数据,环上的点不超过2000个 对于50%的数据 N≤50000. 对于100%的数据 N≤100000.