Iнвестицiї Ледi
Ледi вирiшила стати iнвестором. Вона має у планах iнвестувати в k компанiй по l гривень. Ледi патрiот, тому iнвестує тiльки в компанiї своєї країни. Всього у країнi є n мiст, з’єднаних m дорогами. Вiд кожного мiста можна добратися до всiх iнших по дорогах. Iснує 2^n−1 компанiй. Для кожної непустої множини мiст, iснує одна компанiя, яка має офiс у кожному мiстi з цiєї множини.
У країнi нестабiльна ситуацiя, але оскiльки Ледi розумна, вона iнвестує у компанiю тiльки у тому разi, якщо виконуватиметься наступна умова: у випадку блокування будь-якого одного мiста, всi iншi офiси все одно будуть з’єднанi дорогами. Кожне мiсто i, яке має хоча б один офiс компанiї, в яку iнвестували, приносить pi гривень прибутку. Ледi може iнвестувати менше нiж в k компанiй. Тодi, якщо вона iнвестує в x компанiй, вона отримає додатково (k − x) · l гривень прибутку. Допоможiть Ледi знайти максимальний прибуток.
Вхідні дані
Перший рядок мiстить чотири цiлi числа n, m, k, l (1 ≤ n ≤ 100 000, n − 1 ≤ m ≤ 300 000, 1 ≤ k ≤ 40, 1 ≤ l ≤ 1 000 000 000) — кiлькiсть мiст, кiлькiсть дорiг, кiлькiсть компанiй, в якi планує iнвестувати Ледi, та скiльки гривень iнвестує Ледi в одну компанiю.
Другий рядок мiстить n цiлих чисел p[1], p[2], . . . , p[n] (1 ≤ p[i] ≤ 1 000 000 000) — прибуток i-го мiста.
Наступнi m рядкiв мiстять по два цiлi числа u, v (1 ≤ u ≠ v ≤ n) — номери мiст, мiж якими проведена дорога. Гарантується, що мiж парою мiст може бути максимум одна дорога. Гарантується, що з кожного мiста можна потрапити у кожне iнше по цих дорогам.
Вихідні дані
В єдиному рядку виведiть вiдповiдь на задачу
####Примiтка
У першому прикладi найкращим варiантом буде iнвестувати в компанiю, що має офiси у мiстах 3, 7, 8 та компанiю, що має офiси у мiстах 1, 5, 6.
У другому прикладi найкращим варiантом буде iнвестувати в компанiю, що має офiси у мiстах 1, 2, 3 та компанiю, що має офiси у мiстах 3, 4, 5. I залишити собi l неiнвестованих в третю компанiю гривень.
####Малюнки до прикладiв:
