Legend has it that there is a magic castle. The entire castle can be abstracted as an unrooted tree with $n$ nodes, i.e., an undirected graph with $n$ nodes and $n-1$ edges where any two nodes are connected by a path.

You are a warrior planning to explore the magic castle, starting at node $1$, with an initial attack power of $X$, defense of $0$, and effectively infinite health.

For every other node in the castle, there is either a blue gem that increases defense by $1$, or a monster. For a monster at node $i$, its attack power is $a_i$, defense is $d_i$ ($d_i < X$), and health is $h_i$.

You want to start from node $1$ and traverse all nodes in the castle. The first time you arrive at a node, if it contains a blue gem, your defense increases by $1$; otherwise, you fight the monster at that node. The battle process is as follows:

1. You attack the monster. The damage dealt is your attack power minus the monster's defense. If the monster's health is less than or equal to $0$ at this point, the battle ends; otherwise, proceed to the monster's attack turn.
2. The monster attacks you. Your health decreases by the monster's attack power minus your defense. Note: If the current monster's attack power $a_i$ is less than your defense $Y$, the damage dealt to you is $Y - a_i$, which means your health increases by $Y - a_i$. Since your health is effectively infinite, it will never be less than or equal to $0$. Then, proceed to your attack turn.

After a gem is collected or a monster is defeated at a node, the node becomes empty, and subsequent visits to this node will not trigger any events.

Although your health is effectively infinite, you still want to minimize the total health lost or maximize the total health recovered during the traversal. Formally, let $Del_i$ be the change in your health caused by the monster at node $i$. A negative value represents health lost, and a positive value represents health recovered. If node $i$ contains a blue gem, then $Del_i = 0$. You wish to find a reasonable path to maximize the value of $\sum_{i=2}^{n} Del_i$. Output this maximum value.

Input

The first line contains two integers $n, X$ ($2 \le n \le 10^5, 1 \le X \le 10^6$), representing the size of the tree-shaped magic castle and the warrior's attack power, respectively.

The next $n-1$ lines each contain two integers $u, v$ ($1 \le u, v \le n, u \neq v$), representing an undirected edge between $u$ and $v$ in the tree.

The next $n-1$ lines, for each $i$ from $1$ to $n-1$, first contain an integer $t_i$. If $t_i = 1$, it means node $i+1$ has a blue gem. If $t_i = 2$, it means node $i+1$ has a monster, followed by three integers $a_i, d_i, h_i$ ($1 \le a_i, h_i \le 10^6, 0 \le d_i < X$), representing the monster's attack power, defense, and health, respectively.

Output

Output a single integer representing the maximum total change in health after traversing all nodes.

Examples

Input 1

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

Output 1

-7

Note

The structure of the example tree is shown in the figure below, where nodes $2$ and $5$ contain blue gems, node $3$ contains a monster with attack $1$, defense $0$, and health $3$, and node $4$ contains a monster with attack $3$, defense $1$, and health $5$.

A path that maximizes the total health change:

• Go to node $2$ to collect the blue gem; at this time, the warrior's attack power is $2$, and defense is $1$.
• Go to node $4$ to fight the monster. It is known that the warrior needs $5$ turns to defeat the monster, and the monster will attack the warrior $4$ times. Each time, the warrior loses $2$ health, so the warrior loses $8$ health in total.
• Go to node $5$ to collect the blue gem; at this time, the warrior's attack power is $2$, and defense is $2$.
• Go to node $3$ to fight the monster. It is known that the warrior needs $2$ turns to defeat the monster, and the monster will attack the warrior $1$ time. Each time, the warrior recovers $1$ health, so the warrior recovers $1$ health in total.

In summary, the total change in the warrior's health is $-8 + 1 = -7$.