---
{"category_name":"easy","problem_code":"PRT2","problem_name":"Profitable Paths 2","problemComponents":{"constraints":"","constraintsState":false,"subtasks":"","subtasksState":false,"inputFormat":"","inputFormatState":false,"outputFormat":"","outputFormatState":false,"sampleTestCases":{"0":{"id":1,"input":"3\r\n3 3\r\n1 1 1\r\n1 2\r\n2 3\r\n2 2\r\n1 2\r\n1 2\r\n3 3\r\n1 2 3\r\n1 2\r\n2 3","output":"3\r\n3\r\n8","explanation":"**Example case 3:** We start at vertex $2$, move forward to vertex $3$, then turn around without moving anywhere and end the process. The score is $2 + 3 + 3 = 8$.","isDeleted":false}}},"video_editorial_url":"","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"ahmad_salah","problem_tester":"","date_added":"15-04-2020","tags":{"0":"ahmad_salah","1":"dynamic","2":"easy","3":"greedy","4":"ltime86","5":"rajarshi_basu","6":"trees"},"problem_difficulty_level":"Easy","best_tag":"Dynamic Programming","editorial_url":"","time":{"view_start_date":1595696400,"submit_start_date":1595696400,"visible_start_date":1595696400,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=PRT2","is_proctored":false,"visitedContests":{},"layout":"problem"}
---
### Read problem statements in [Hindi](https://www.codechef.com/download/translated/LTIME86/hindi/PRT2.pdf), [Bengali](https://www.codechef.com/download/translated/LTIME86/bengali/PRT2.pdf), [Mandarin Chinese](https://www.codechef.com/download/translated/LTIME86/mandarin/PRT2.pdf), [Russian](https://www.codechef.com/download/translated/LTIME86/russian/PRT2.pdf), and [Vietnamese](https://www.codechef.com/download/translated/LTIME86/vietnamese/PRT2.pdf) as well.
You are given a tree with $N$ vertices (numbered $1$ through $N$) and a sequence of integers $A_1, A_2, \ldots, A_N$. You may choose an arbitrary permutation $p_1, p_2, \ldots, p_N$ of the integers $1$ through $N$. For each valid $i$, you should assign the value $A_{p_i}$ to vertex $i$.
Then, you should choose a vertex of the tree and $K-1$ times, perform one of the following operations:
- Move forward — move to a vertex which is adjacent to your current vertex. However, you must not move to the vertex in which you were immediately before the previus operation (if it exists).
- Turn around — stay in your current vertex. You may only do this if it is impossible to move forward. Since you do not move in this operation, you may move forward again afterwards.
In this process, you obtain a sequence of vertices $v_1, v_2, \ldots, v_K$ — the initial vertex and the vertices in which you were after each operation. Your *score* is $\sum_{i=1}^K A_{p_{v_i}}$. What is the maximum possible value of this score?
### Input
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $K$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.
- Each of the following $N-1$ lines contains two space-separated integers $u$ and $v$ denoting that vertices $u$ and $v$ are connected by an edge.
### Output
For each test case, print a single line containing one integer — the maximum possible score.
### Constraints
- $1 \le T \le 1,000$
- $2 \le N \le 300,000$
- $1 \le K \le 10^9$
- $1 \le A_i \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $5 \cdot 10^5$
### Subtasks
**Subtask #1 (50 points):**
- $N \le 1,000$
- $K \le 2,000$
- the sum of $N$ over all test cases does not exceed $2,000$
- the sum of $K$ over all test cases does not exceed $2,000$
**Subtask #2 (50 points)**: original constraints
### Example Input
```
3
3 3
1 1 1
1 2
2 3
2 2
1 2
1 2
3 3
1 2 3
1 2
2 3
```
### Example Output
```
3
3
8
```
### Explanation
**Example case 3:** We start at vertex $2$, move forward to vertex $3$, then turn around without moving anywhere and end the process. The score is $2 + 3 + 3 = 8$.
<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>