Given a tree of N nodes and N - 1 edges rooted at node 1, with exactly one candy placed at each node. Let's say the cost of the candy placed on the i^th node is A_i. You have K amount of money. Now, you will choose exactly one node (say u) and will start buying the candies placed on the path from node u to the root until you run out of money, that is, first, you will buy the candy placed at node u, then the candy placed at the ancestor of u, then its ancestor and so on until you run out of money or you reach root node. Also, you cannot skip over a node without buying the candy placed at that node.

Calculate the maximum number of candies in a given amount of money you can buy by choosing exactly one starting node.

Notes

• A graph is connected if, for each pair of nodes u and v, there exists a path between these two nodes in the graph.
• A tree is a connected graph with N nodes and N - 1 edges.

Function description

Complete the solve function. This function takes the following 4 parameters and returns an Integer.