Charlie’s Apple Tree Adventure

Charlie loved climbing trees in his childhood. One day, he decided to challenge a tall apple tree which has \(n\) nodes, with node \(1\) being the root. Each node either has a number of apples or hosts a bird nest. When Charlie visits a node for the first time:

• If the node has apples (an apple node), he picks all the apples there and adds them to his pocket.
• If the node is a bird nest (a nest node), he must give one apple to each bird in the nest. However, if his current apple count is less than the number of birds \(b\) at that node, he will not go there.

Note that if Charlie passes through a node more than once, the operation on that node (collecting apples or giving apples) is performed only once. Initially, Charlie starts with \(s\) apples. Beginning from the root, he travels along the edges of the tree – each time he moves from one node to an adjacent node, he performs the corresponding operation immediately upon arrival (including at the root). Charlie can decide the order in which to visit the subtrees (subject to the tree structure) and may choose to skip some branches. His goal is to finish his climb with as many apples as possible.

Your task is to help Charlie plan his climbing route so that he maximizes the number of apples in his pocket at the end.

Input constraints and notes:
All numbers in the input are integers. For a node that is an apple node, the given value represents the number of apples available. For a nest node, the given value represents the number of birds (and thus the number of apples that must be spent, exactly one per bird) when visiting it for the first time. The tree is unrooted but node 1 is considered the root. An edge exists between two nodes if they are connected. Note that if Charlie cannot pay the cost at a nest node, he will simply not enter that part of the tree.

Formulas are given in LaTeX format.

inputFormat

The input is given as follows:

 n s
 a_1 v_1
 a_2 v_2
 ...
 a_n v_n
 u_1 v_1
 u_2 v_2
 ...
 u_{n-1} v_{n-1}

Here, the first line contains two integers \(n\) and \(s\) where \(n\) is the number of nodes in the tree and \(s\) is the initial number of apples. The next \(n\) lines describe each node. For the \(i\)-th node, \(a_i\) is an integer indicating the type of the node (0 for an apple node and 1 for a nest node) and \(v_i\) is the corresponding value (i.e. the number of apples available if \(a_i=0\) or the number of birds if \(a_i=1\)). The following \(n-1\) lines each contain two integers \(u\) and \(v\), indicating that there is an edge between nodes \(u\) and \(v\>.

outputFormat

Output a single integer, which is the maximum number of apples Charlie can have after his climb.

If there is no feasible way to visit any further node (due to insufficient apples for a nest), the current apple count may be considered the final answer.

sample

3 5
0 3
1 4
0 2
1 2
1 3

10