Investments Lady

The lady has decided to become an investor and plans to invest in k companies, allocating l hryvnias to each. As a patriot, she will only invest in companies based in her own country. The country consists of n cities, interconnected by m 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 i with an office of the invested company generates pi hryvnias in profit. If she invests in fewer than k companies, she earns an additional profit of (k − x) · l hryvnias, where x is the number of companies she invests in. Your task is to help her maximize her profit.

Input Format

The first line contains four integers n, m, k, l (1 ≤ n ≤ 100,000, n − 1 ≤ m ≤ 300,000, 1 ≤ k ≤ 40, 1 ≤ l ≤ 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 n integers p[1], p[2], ..., p[n] (1 ≤ p[i] ≤ 1,000,000,000) — the profit from the i-th city.

The following m lines each contain two integers u, v (1 ≤ u ≠ v ≤ n) — indicating a road between cities u and v. 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 Format

Output the maximum possible profit on a single line.

Examples

Note

In the first example, the optimal strategy is to invest in the company with offices in cities 3, 7, 8 and the company with offices in cities 1, 5, 6.

In the second example, the best choice is to invest in the company with offices in cities 1, 2, 3 and the company with offices in cities 3, 4, 5, while keeping the investment for the third company unallocated to gain additional profit.

Illustrations for examples: