小李开店

题目描述

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

输入

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

输出

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

样例

提示

【数据范围】