You are given a tree consisting of n nodes and rooted at node 1. Each node of the tree is colored either black or white and also has a certain joy value associated with it. Your task is to find a connected subgraph of this tree containing exactly i black nodes and having maximum joy value for each i ranging from 1 to n .

Some definitions:
A subgraph of the tree is a graph whose vertex set(S) is a subset of the nodes of the original tree and consists of exactly those edges of the original tree whose both end points are present in S.
Joy value of a subgraph is the sum of joy values of all nodes present in the subgraph.

Input format
First line: n denoting the number of tree nodes
Next n-1 lines, each contain 2 integers representing a tree edge.
Next line contains n integers denoting the color of the nodes. Black color is denoted by 1 and white color by 0.
Next line contains n integers denoting the joy values of the nodes.

Output format
Output the maximum joy value of a connected subgraph containing exactly i nodes for each i from 1 to n, each on a new line.
If for some i, there is no connected subgraph consisting of exactly i black nodes, output "Not Found"(without quotes) instead.

Constraints
\(1\le n\le 5000\)
\(-10^9\le Joy Value\le 10^9\)