题目背景

一座城市，往往会被人们划分为几个区域，例如住宅区、商业区、工业区等等。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