Maximizing Mining Output in a Tree‐Structured Mine

You are the owner of a mining pit organized in a tree structure with n nodes. Node 1 is the surface. For every node i (2 ≤ i ≤ n) there is a corridor connecting it with a shallower node f_i (with f_i < i). Moreover, every node f appears at most twice as a parent. Each non‐surface node has two distinct values: a robot production rate r_i and a human production rate p_i. (The surface, node 1, produces nothing.)

You control one robot initially located at node s; there are no humans in the mine at the start. The mine is extremely narrow: each node may hold at most one worker (robot or human) and every corridor allows exactly one worker to move through at a time. At any moment at most one worker may be moving along a corridor while all others must be stationed at nodes.

You have to execute q plans in order. Each plan consists of four phases:

1. Preparation: Humans may move arbitrarily among nodes (subject to the movement constraints) but cannot enter or leave the mine. The robot does not move in this phase.
2. Execution: There are 4 types of plans:
   1. The robot must move upwards (toward shallower nodes) along one or more corridors. Humans do not move.
   2. The robot must move downwards (toward deeper nodes) along one or more corridors. Humans do not move.
   3. A human enters the mine from the surface. (This requires that node 1 is empty at the start of this phase.) No other movement occurs.
   4. A human exits the mine from the surface. (This requires that node 1 is occupied by a human at the start of this phase.) No other movement occurs.
3. Adjustment: Again, humans may move arbitrarily (obeying the same rules as in preparation and without leaving or entering the mine). The robot does not move.
4. Extraction: Each worker extracts one unit of ore per unit time. If a worker is at a non‐surface node i, its extraction rate is r_i if it is a robot and p_i if it is a human. Nodes without any worker produce nothing. The total yield of the plan is the sum of extractions over all nodes.

Your task is to plan the moves (in all phases) so that, after executing all q plans in order, the overall ore yield is maximized. Note that because humans may move arbitrarily in the preparation and adjustment phases, you can assume that at extraction time the humans will be placed on the best available nodes. Specifically, if there are H humans in the mine at extraction time and the robot occupies one node, then the humans can be assigned to the H nodes with the largest human production rates (p_i) among all nodes except the one occupied by the robot.

Input constraints and notes:

• The values r_i and p_i (for i ≥ 2) are all distinct.
• When the robot moves (in phases 2 and 3 of execution), it must follow a valid corridor path: upward moves require moving from the current node to one of its ancestors (excluding the current node) while downward moves require moving to a descendant (excluding the current node).
• The plans of type 3 and 4 change the number of humans in the mine by +1 and -1 respectively.

Input Format: described below.

Output Format: Print the maximum total yield obtainable over the q plans.

inputFormat

The first line contains two integers n and q (number of nodes and number of plans).

The second line contains an integer s (the starting node of the robot).

Then follow n-1 lines. For each node i from 2 to n, the i-th line contains three integers: f_i (the parent node), r_i (the robot production rate at node i), and p_i (the human production rate at node i).

Then follow q lines, each containing a single integer t (1 ≤ t ≤ 4) representing the type of the plan:

1. Robot moves upward.
2. Robot moves downward.
3. Insert one human from the surface.
4. Remove one human to the surface.

outputFormat

Output a single integer representing the maximum total yield obtainable after executing all q plans in order.

sample

3 3
2
1 5 3
1 7 4
3
1
2

23