Инвестиции Леди

Леди решила стать инвестором. Она планирует вложить средства в k компаний, инвестируя в каждую по l гривен. Леди патриотична, поэтому инвестирует только в компании своей страны. В стране есть n городов, соединенных m дорогами. Из любого города можно добраться до всех остальных по дорогам. Существует 2^n−1 компаний. Для каждого непустого множества городов существует компания, которая имеет офис в каждом городе из этого множества.

В стране нестабильная ситуация, но Леди умна и инвестирует в компанию только при выполнении следующего условия: если любой один город будет заблокирован, все остальные офисы должны оставаться соединенными дорогами. Каждый город i, в котором есть хотя бы один офис компании, в которую инвестировали, приносит pi гривен прибыли. Леди может инвестировать в меньшее количество компаний, чем k. В таком случае, если она инвестирует в x компаний, она получит дополнительно (k − x) · l гривен прибыли. Помогите Леди найти максимальную прибыль.

Формат входных данных

Первая строка содержит четыре целых числа n, m, k, l (1 ≤ n ≤ 100 000, n − 1 ≤ m ≤ 300 000, 1 ≤ k ≤ 40, 1 ≤ l ≤ 1 000 000 000) — количество городов, количество дорог, количество компаний, в которые планирует инвестировать Леди, и сумма инвестиций в одну компанию.

Вторая строка содержит n целых чисел p[1], p[2], ..., p[n] (1 ≤ p[i] ≤ 1 000 000 000) — прибыль i-го города.

Следующие m строк содержат по два целых числа u, v (1 ≤ u ≠ v ≤ n) — номера городов, между которыми проведена дорога. Гарантируется, что между любой парой городов может быть максимум одна дорога. Гарантируется, что из каждого города можно попасть в любой другой по этим дорогам.

Формат выходных данных

В единственной строке выведите ответ на задачу.

Примеры

Примечание

В первом примере наилучшим вариантом будет инвестировать в компанию, которая имеет офисы в городах 3, 7, 8, и в компанию, которая имеет офисы в городах 1, 5, 6.

Во втором примере наилучшим вариантом будет инвестировать в компанию, которая имеет офисы в городах 1, 2, 3, и в компанию, которая имеет офисы в городах 3, 4, 5. И оставить себе l неинвестированных в третью компанию гривен.

Рисунки к примерам: