问题描述
众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习。但是今天六花酱不想做数学题，于是他们开始玩游♂戏：
很久很久以前，有一块圣地亚哥大陆，大陆上有$n$个生产金坷垃的城市和$n-1$条道路。每一对城市都可以通过这些道路相互到达。
现在你想要建立你自己国家并让你的故乡——1号城市成为首都。接着你会切断所有连接着在你国家中的城市和不在你国家中的城市的道路。为了社会的稳定，你的国家必须满足：
1.1号城市必须在你的国家中。
2.你的国家中的每一对城市都可以通过还没有被切断的道路相互到达。
实际上，在切断了道路之后，圣地亚哥大陆被分成了很多个联通块。每一个联通块都发展成了一个国家。为了世界的和平，你打算选择至多$k$个其他的国家（当然不可能是自己的国家了）建立外交关系。
每一个城市都有一个繁荣值$w_i$，每一个国家的繁荣值等于在这个国家中的所有城市的繁荣值之和。你建立的国家稳定值等于你的国家的繁荣值加上$a \times$所有和你建立外交关系的国家的繁荣值之和。
为了增加金坷垃的产量，你需要最大化你的国家的稳定值。
当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？
输入描述
数据组数不超过1000组且只有不超过3组数据有$n,k \geq 100$.
对于每组数据，第一行是三个整数$n,a,k(1 \leq n \leq 10^5, -10^3 \leq a \leq 10^3, 0 \leq k \leq 500)$.
第二行有$n$个整数$w_i(-10^9 \leq w_i \leq 10^9)$
接下来$n$行。每行两个整数$u,v(1 \leq u,v \leq n)$，代表给定图上的一条边。
输出描述
对于每一组数据，输出一行一个整数表示答案。
输入样例
3 2 1
10 100 1000
1 2
1 3
输出样例
2110
Hint
你的国家是{1,2}，然后和国家{3}建立外交关系。这样你的国家稳定值是2110.
