Інвестиції Леді#9091

Інвестиції Леді

1 секунда

64 мегабайти

Дуже складна

Леді вирішила стати інвестором. Вона має у планах інвестувати в $k$ компаній по $l$ гривень. Леді патріот, тому інвестує тільки в компанії своєї країни. Всього у країні є $n$ міст, з'єднаних $m$ дорогами. Від кожного міста можна добратися до всіх інших по дорогах. Існує $2^{n} - 1$ 2^n - 1 компаній. Для кожної непустої множини міст, існує одна компанія, яка має офіс у кожному місті з цієї множини.

У країні нестабільна ситуація, але оскільки Леді розумна, вона інвестує у компанію тільки у тому разі, якщо виконуватиметься наступна умова: у випадку блокування будь-якого одного міста, всі інші офіси все одно будуть з'єднані дорогами. Кожне місто $i$ , яке має хоча б один офіс компанії, в яку інвестували, приносить $p_{i}$ p_i гривень прибутку. Леді може інвестувати менше ніж в $k$ компаній. Тоді, якщо вона інвестує в $x$ компаній, вона отримає додатково $(k - x) \cdot l$ (k - x) \cdot l гривень прибутку. Допоможіть Леді знайти максимальний прибуток.

Вхідні дані

Перший рядок містить чотири цілі числа $n$ , $m$ , $k$ , $l$ ( $1 \leq n \leq 100000$ 1 \leq n \leq 100\ 000, $n - 1 \leq m \leq 300000$ n - 1 \leq m \leq 300\ 000, $1 \leq k \leq 40$ 1 \leq k \leq 40, $1 \leq l \leq 1000000000$ 1 \leq l \leq 1\ 000\ 000\ 000) — кількість міст, кількість доріг, кількість компаній, в які планує інвестувати Леді, та скільки гривень інвестує Леді в одну компанію.

Другий рядок містить $n$ цілих чисел $p_{1}, p_{2}, \dots, p_{n}$ p_1, p_2, \ldots, p_n ( $1 \leq p_{i} \leq 1000000000$ 1 \leq p_i \leq 1\ 000\ 000\ 000) — прибуток $i$ -го міста.

Наступні $m$ рядків містять по два цілі числа $u$ , $v$ ( $1 \leq u \neq = v \leq n$ 1 \leq u \neq v \leq n) — номери міст, між якими проведена дорога. Гарантується, що між парою міст може бути максимум одна дорога. Гарантується, що з кожного міста можна потрапити у кожне інше по цих дорогах.

Вихідні дані

В єдиному рядку виведіть відповідь на задачу.

Приклади

Приклад 1

Приклад 2

Примітка

У першому прикладі найкращим варіантом буде інвестувати в компанію, що має офіси у містах $3$ , $7$ , $8$ та компанію, що має офіси у містах $1$ , $5$ , $6$ .

У другому прикладі найкращим варіантом буде інвестувати в компанію, що має офіси у містах $1$ , $2$ , $3$ та компанію, що має офіси у містах $3$ , $4$ , $5$ . І залишити собі $l$ неінвестованих в третю компанію гривень.

Малюнки до прикладів: