Fax McClad, Croneria's richest bounty hunter, has enough reward money to start investing. He would like to invest in companies that will bring him a lot of profit. He will invest ~I~ moneys in each company he chooses to invest in, and he will invest in no more than ~K~ companies.

Looking at a map of the Lylot System, there are ~N~ planets, with ~M~ bi-directional spaceroads that connect them.

Ding dong!

Already, ~2^N-1~ companies line up at Fax's door to ask for his money! All of the companies sell the same products, so the only difference between them is the placement of their offices. Specifically, for each non-empty subset of planets, there is ~1~ company that has an office in those planets and only those planets.

However, since the galaxy is full of conflict, Fax is forced to only choose companies that fit the following condition: if any single planet gets destroyed, the remaining offices of that company should remain connected.

After ruling out all the companies that don't fit the condition, he moves on to maximize his profits. For every planet that hosts at least one office of a company that Fax has invested in, he will receive profit. In particular, the ~i^\text{th}~ planet will give him ~p_i~ moneys as profit. Note that any moneys that Fax does not use to invest count as profit as well.

Can you help Fax determine what his maximum profit will be?

Constraints

~1 \le N \le 150\,000~

~N-1 \le M \le 500\,000~

~1 \le K \le 20~

~0 \le I \le 1\,000\,000\,000~

~1 \le u, v \le N~

~1 \le p_i \le 1\,000\,000\,000~ for all ~1 \le i \le N~

It is guaranteed that there will be at most 1 road between every pair of planets.

Subtask	Constraint	Points
1	~N \le 10~	10
2	~N \le 50~, ~K \le 5~	20
3	~M = N-1~	15
4	~I = 0~	30
5	No additional constraints	25

Input Specification

The first line of input will contain four space-separated integers, ~N~, ~M~, ~K~, and ~I~.

~M~ lines of input follow. Each line will contain two space-separated integers in the form u v, signifying that there exists a bi-directional spaceroad connecting planet ~u~ and planet ~v~.

The last line will contain ~N~ space-separated integers, denoting ~p_1, p_2, \dots, p_N~.

Output Specification

On a single line, output the maximum profit that Fax can receive.

Sample Input 1

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

Sample Output 1

22

Sample Explanation 1

The best solution is to invest in the company that has offices at cities 1, 2, 3, 4.

Sample Input 2

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

Sample Output 2

28

Sample Explanation 2

The best solution is now to first invest in the company that owns offices in the cities 3, 7, 8, then invest in the company that owns offices at 1, 5, 6.

Sample Input 3

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

Sample Output 3

55

Sample Explanation 3

The best solution is to invest in the company that owns offices in the cities 1, 2. Then, invest in the company that owns offices in the cities 3, 4, 5. Finally, keep the last ~I = 5~ dollars and don't invest it.