A country has been divided into $n$ states and each state has plenty of resources. All these states are connected with each other by using $(n-1)$ pathways. You can travel to any state from another state by using these pathways. Your task is to extract resources from states.

You are given a list of $m$ states and you have to start your journey from any one of these states. After starting your journey, you will start extracting the resources from the states one by one while visiting them using the pathways. You are also provided with an energy level $k$ where $k$ is your initial energy level. This energy level is decreased by one whenever you use a pathway. If your energy level becomes zero, then you cannot extract resources anymore.

You will be provided with all the information of the country, list of the $m$ states and the initial energy level $k$. Determine the maximum sum of resources that you can extract from the states during your journey. 

Note: You can not visit any state more than once during your journey. Besides, you can also select not to extract resources from any of the states. In that case, the total sum of resources will be zero.

Input format

• First line: A single integer $t$ that denotes the number of test cases.
• For each $t$ test case:
  • First line: Three integers $n$, $m$, and $k$ where $n$ is the total number of states, $m$ is the number of states you can start your journey from, and $k$ is your initial energy level when you start your journey
  • Next line: An array $p$ of $n$ integers where the $i^{th}$ integer represents the number of resources in the $i^{th}$ state
  • Next $n-1$ lines: Two integers $u$ and $v$ that indicates a pathway between the states $u$ and $v$
  • Last line: $n$ integers which are either $0$ or $1$. If the $i^{th}$ integer is $1$, then you can start your journey from $i^{th}$ state otherwise you cannot start your journey from that state

Output format

For each of the test case, print a single integer that represents the maximum number of extracted resources.

Input Constraints

• $1 \le t \le 50$
• $1 \le n \le 10^6$
• $1 \le m,k \le n$
• $1 \le u,v \le n$
• $-10^9 \le p_i \le 10^9$
• Sum of $n$ over all test cases $\le10^6$