Политичките партии претставуваат здруженија на граѓани со исти политички убедувања, кои се стремат да дојдат на власт за да ги остварат заедничките цели. Во Македонија, политичките партии се организирани хиерархиски - на чело е лидерот на партијата, директно под него неговите најблиски соработници, итн. Сите членови се дел од единствената хиерархија на партијата, која е дефинирана со N-1 врски (види слика), каде N е бројот на членови.

При официјално исклучување на кој било член од партијата, а поради блискоста со нивниот раководител и намалената моќ која што тие ќе ја имаат во иднина, од партијата веднаш си одат и сите членови кои се наоѓаат (едно или повеќе нивоа) под него во хиерархијата на партијата - без да има потреба од нивно официјално исклучување.

Вам ви се дадени информации за една политичка партија, со N членови. Со број 1 е означен лидерот на партијата. За секој член на партијата, познато е неговото влијание кај народот (цел број - кој може да биде позитивен или негативен). Влијанието на партијата кај народот е сумата од влијанијата на сите нејзини членови.

Кое е максималното влијание кое што може да го има партијата, по официјално исклучување на најмногу К нејзини членови?

Влез

Во првата линија се запишани два цели броја N (2 <= N <= 50 000) и K (1 <= K <= 150).

Во втората линија се запишани N цели броеви Vi (-1 000 000 000 <= Vi <= 1 000 000 000), кои го означуваат влијанието на секој член на партијата (почнувајќи со членот со број 1, па членот со број 2, итн).

Во следните N-1 редови се запишани по два цели броја Xi и Yi (1 <= Xi < Yi <= N), кои ги дефинираат врските помеѓу членовите.

Излез

Отпечатете го бараното максимално влијание.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 512 megabytes

Примери

влез
7 1
5 9 -1 -4 -5 2 -7
1 5
1 4
1 3
2 5
4 6
4 7

излез
8

влез
7 2
5 9 -1 -4 -5 2 -7
1 5
1 4
1 3
2 5
4 6
4 7

излез
9

влез
3 2
2 2 2
1 2
1 3

излез
6

Објаснување за првите два примери: Види слика.

Објаснување за третиот пример: Можно е да се исклучат и помалку од K членови.