Investments Lady#9091
The lady has decided to become an investor and plans to invest in companies, allocating hryvnias to each. As a patriot, she will only invest in companies based in her own country. The country consists of cities, interconnected by roads, allowing travel between any two cities. There are 2^n - 1 potential companies, each corresponding to a non-empty subset of cities where the company has offices.
Given the country's instability, the lady will only invest in a company if, even with one city blocked, the remaining offices are still connected by roads. Each city with an office of the invested company generates p_i hryvnias in profit. If she invests in fewer than companies, she earns an additional profit of (k - x) \cdot l hryvnias, where is the number of companies she invests in. Your task is to help her maximize her profit.
The first line contains four integers , , , (1 \leq n \leq 100\ 000, n - 1 \leq m \leq 300\ 000, 1 \leq k \leq 40, 1 \leq l \leq 1\ 000\ 000\ 000) — representing the number of cities, the number of roads, the number of companies she plans to invest in, and the investment amount per company.
The second line contains integers p_1, p_2, \ldots, p_n (1 \leq p_i \leq 1\ 000\ 000\ 000) — the profit from the -th city.
The following lines each contain two integers , (1 \leq u \neq v \leq n) — indicating a road between cities and . It is guaranteed that there is at most one road between any pair of cities, and all cities are reachable from one another through these roads.
Output the maximum possible profit on a single line.
Exemple 1
Exemple 2
In the first example, the optimal strategy is to invest in the company with offices in cities , , and the company with offices in cities , , .
In the second example, the best choice is to invest in the company with offices in cities , , and the company with offices in cities , , , while keeping the investment for the third company unallocated to gain additional profit.
Illustrations for examples:
