My Lion Paintings

I painted lion pictures and displayed them in a museum shaped like a tree. The museum has several rooms connected by passages, and each room holds one painting. If the rooms are vertices and the passages are edges, the graph is a tree. Room 1 is the root, and it has the door where visitors enter and leave.

Someone broke in and made every lion painting look like a bear. I painted exactly N lion paintings, and there are K kinds of them. Repairing one painting of kind i takes $C_i$ time. Paint is limited, so at most $P_i$ paintings of kind i can be repaired.

Root the tree at room 1 and pick one room as the work room. You can repair only the paintings in the subtree rooted at the work room. Each time you finish a job you must return to the work room, so if a painting is at distance d from the work room, the job costs an extra d time. You can work for M time in total. For each room chosen as the work room, find the maximum number of paintings you can repair so that the total work time does not exceed M.

The first line contains N, K, and M. ($1 \le K \le N \le 2 \times 10^5$, $1 \le M \le 10^{15}$)

The next N-1 lines describe the passages. The i-th line contains the number of the parent room of room i+1 and the distance from that parent room, separated by a space. ($1 \le$ passage length $\le 10^5$)

The next line contains N numbers, where the i-th number is the kind of painting in room i. ($1 \le$ painting kind $\le K$)

The next line contains K numbers, where the i-th number is $C_i$. ($1 \le C_i \le M$)

The next line contains K numbers, where the i-th number is $P_i$. ($1 \le P_i \le N$)

On the i-th line, print the maximum number of paintings you can repair when room i is the work room.