eolymp
bolt
Try our new interface for solving problems
Məsələlər

Iнвестицiї Ледi

Iнвестицiї Ледi

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Лед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 знайти максимальний прибуток.

Giriş verilənləri

Перший рядок м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нше по цих дорогам.

Çıxış verilənləri

В єдиному рядку вивед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в:

F.jpg

Nümunə

Giriş verilənləri #1
8 10 2 5
10 1 10 1 2 2 2 2
1 2
2 3
3 4
4 1
1 5
5 6
6 1
3 7
7 8
8 3
Çıxış verilənləri #1
28
Giriş verilənləri #2
6 7 3 5
10 10 10 10 10 1
1 2
2 3
1 3
3 4
4 5
3 5
5 6
Çıxış verilənləri #2
55
Mənbə 2019-2020 ACM-ICPC, SEERC, 1/4 фiналу, Днiпро, Київ, Львiв, Миколаїв, Тернопiль, Харкiв, 14 вересня 2019