Ardi, The Hungry Aardvark

Ardi the aardvark arrived at the pet shop tired and hungry. On the next shelf she spotted an ant farm already populated with lots of yummy-looking crispy ants. The farm was so 2-dimensional that she could see every tunnel and every ant. Ardi immediately began plotting how to satisfy her hunger after the shop closes. Her tongue is 30 cm long, which is typical for aardvarks. She can estimate the lengths of the tunnel sections and count the ants in them. Her objective is to get in and out as quickly as possible, using a limited number of probes with her long tongue, to reach the maximum number of ants. Ardi wants your help with the analysis, since aardvarks are not known for their computing prowess.

In preparation for her meal, Ardi wants you to consider multiple (not necessarily all) maximal-length paths that her tongue can take into the tunnels. With these calculations done in advance, she can choose the optimal paths to probe during her limited feeding time.

There is a single entrance to the ant hill, labeled 'a'. At that point the tunnel forks into at most two branches, leading left or right. Each branch may subdivide similarly at intersections further down. For each listed maximal-length path, Ardi records the length of each tunnel segment and the direction to take at each intersection, using L (left) and R (right), relative to the direction her tongue is probing. She does not record segments that are entirely beyond the 30 cm reach of her tongue. A probe ends either at a dead end or in the middle of a segment at the full reach of her tongue. The tunnels are too narrow for her tongue to double back during the same probe, so it cannot go down a different branch in that probe. Ardi records the number of reachable ants in each segment of each path. Your task is to calculate the maximum total number of ants her tongue can reach.

The first line contains two integers: the number of paths Ardi has recorded, and the number of probes she has time to complete. Each following line describes one maximal-length path, given in no particular order. A path line begins with its number of segments. Then come the segments in order. Each segment has four components: the letter R (right turn) or L (left turn), the estimated full length of the segment (a positive integer, even if its far end is beyond her reach), the number of reachable ants in the segment (there may be more beyond her reach), and a lowercase letter naming the node at the far end of the segment. The node may be an intersection or a dead end. Nodes are named in the order they are first examined, starting with a.

Ardi will never ask for more than 20 probes. No node or segment is repeated within the same probe. No two candidate paths merge further down a path. No tunnel segment holds more than 100 ants.

Print a single integer: the maximum number of ants Ardi can catch with the given number of probes, using some combination of the provided maximal paths.

The figure in the original statement shows the sample configuration. Path 2 (abdef) reaches 4+7+3+1=15 ants, so with one probe the maximum is 15. With two probes, paths 2 (abdef) and 6 (aik) are fully disjoint, and paths 3 (abdeg) and 4 (abdh) each hold more ants than path 2. However, many of their ants are already taken by the probe of path 6, so the 27 ants from paths 2 and 6 are optimal.