Art Gallery Heist

The art museum is composed of several exhibition halls and corridors. Every corridor ends either in an exhibition hall or splits into two corridors. Each hall contains several paintings, each with an associated value. Traversing a corridor and stealing a painting both consume time.

You are given an overall time limit of \(n\) seconds, after which the police will arrive at the entrance. You start inside the museum and must plan a route that starts and ends at the entrance. In each corridor you traverse, you spend \(d\) seconds per corridor (both ways) and each painting stolen costs \(s\) seconds. While in a hall you may choose to steal any number of paintings (each painting takes exactly \(s\) seconds to steal, and you may take them in any order; it is optimal to take the most valuable paintings first).

The layout of the museum is given in a recursive, prefix order format. A node in the description is either:

• Hall (Leaf): denoted by L followed by an integer k (the number of paintings) and then k integers representing the values of the paintings.
• Corridor Split: denoted by N followed by two subtrees (each subtree is described in the same format).

Your task is to compute the maximum total value you can steal without getting caught – that is, the maximum total value you can obtain by planning a route that starts and ends at the entrance within \(n\) seconds.

Note: When moving from a node to one of its children, you incur an additional cost of \(d\) seconds each way. When stealing a painting in a hall, you incur a time cost of \(s\) seconds per painting. You may choose to visit one or both branches at any corridor split.

The optimization can be solved using a tree dynamic programming strategy. For a hall node, if you have \(T\) seconds available, you can steal at most \(\lfloor T/s \rfloor\) paintings (choosing the most valuable ones first). For an internal (corridor) node with two children having DP solutions, you decide whether to visit only one child (incurring a cost of \(2d\)) or both children (incurring a cost of \(4d\)) and split the remaining time between them in an optimal way.

All formulas are given in LaTeX format.

inputFormat

The first line contains three integers: \(n\), \(d\), and \(s\) — the total available time (in seconds), the time to traverse one corridor (one way), and the time to steal one painting, respectively.

The second line contains the museum description in prefix order. The description is given as a sequence of tokens separated by spaces.

Each node in the description is either:

• L k v1 v2 ... vk for a hall node (leaf), where k is the number of paintings and vi are their values.
• N for a corridor split node, followed by the descriptions of its two children.

outputFormat

Output a single integer: the maximum total value you can steal while starting and ending at the entrance within \(n\) seconds.

sample

10 1 1
L 3 5 2 1

8