Карам уже год работает директором и решил привнести что-то новое. Он хочет изменить способ посадки в классах. Так как Карам в школьные годы любил деревья, он решил, что места посадки в классе будут представлять собой дерево. Всего класс вмещает в себя $$$n$$$ учеников, но для большего комфорта Карам решил, что в кабинете будет учиться ровно $$$k$$$ учеников.
Карам создал метрику, по которой он будет оценивать рассадку в кабинете. А именно:
- Каждая парта получила свою ценность $$$a_i$$$, если за этой партой будет сидеть ребёнок, то оценка рассадки будет увеличена на $$$a_i$$$.
- Карам не очень любит, когда дети списывают, поэтому он за каждую пару детей, сидящих рядом, будет уменьшать оценку рассадки на $$$C$$$.
Карам хочет узнать максимально возможную ценность рассадки в кабинете.
В первой строке ввода даны 3 целых числа $$$n,k$$$ $$$(1 \le k \le n \le 2000)$$$ и $$$C$$$ $$$(0 \le C \le 10^9)$$$ — количество парт и детей соответственно, а также штраф за пару сидящих рядом детей.
Во второй строке ввода даны n чисел $$$a_1,a_2,...,a_n$$$ $$$(0 \le a_i \le 10^9)$$$ — ценности парт.
Далее следует $$$n-1$$$ строка с 2 целыми числами $$$u_i, v_i$$$ $$$(1 \le u_i \lt v_i \le n)$$$ — описание кабинета, пара $$$(u_i,v_i)$$$ означает, что парты $$$u_i$$$ и $$$v_i$$$ являются соседними.
Выведите ответ на задачу.
Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы.
| Группа | Дополнительные ограничения | Баллы | Необходимые подгруппы |
| $$$0$$$ | Тесты из условия | $$$0$$$ | — |
| $$$1$$$ | $$$1 \le n \le 20$$$ | $$$7$$$ | $$${0}$$$ |
| $$$2$$$ | $$$C = 0$$$ | $$$5$$$ | — |
| $$$3$$$ | $$$1 \le k \le 2$$$ | $$$9$$$ | — |
| $$$4$$$ | $$$u_i + 1 = v_i$$$ | $$$19$$$ | — |
| $$$5$$$ | $$$1 \le n \le 50$$$ | $$$15$$$ | $$${0}$$$ |
| $$$6$$$ | $$$1 \le n \le 300$$$ | $$$19$$$ | $$${0,1,5}$$$ |
| $$$7$$$ | — | $$$26$$$ | $$${0,1,2,3,4,5}$$$ |
5 3 35 5 3 2 41 22 32 44 5
12
5 4 102 2 2 2 21 22 33 44 5
-12
Оптимальные рассадки в 1 и 2 примерах, жирным выделены парты, на которые сядут ученики.
Оптимальная рассадка в 1 примере, оценка рассадки равна $$$a_1+a_3+a_5-0 \cdot C= 5 + 3 + 4 = 12$$$ 
Оптимальная рассадка во 2 примере, оценка рассадки равна $$$a_1+a_2+a_4+a_5 - 2 \cdot C = 2 + 2 + 2 + 2 - 2 \cdot 10 = -12$$$
