P3360 Steal the Sky, Swap the Sun

A master thief covets the masterpieces in the art museum and is ready for a big haul.

The art museum consists of several exhibition rooms and several corridors. Each corridor either ends at an exhibition room, or splits into two corridors. Each exhibition room contains several paintings, and each painting has a value. Traversing a corridor and stealing a painting both take time. The police will arrive at the entrance in $n$ seconds. Find the maximum total value you can obtain without being caught. 

- The first line contains an integer $n$ ($n \leq 600$). - Starting from the second line, a sequence is given in depth-first order. For each entry, read a pair $(t, x)$: - $t$ is the time in seconds to either enter an exhibition room or traverse a corridor. - If $x > 0$, the corridor leads to an exhibition room containing $x$ paintings, followed by $x$ pairs $(w, c)$, where stealing one painting of value $w$ takes $c$ seconds. - If $x = 0$, the corridor splits into two sub-corridors; the descriptions of these two sub-corridors follow immediately in depth-first order. - Constraints: $t, c \leq 5; x \leq 30$. - The numbers of rooms and corridors do not exceed $300$. - The input is given in depth-first order.

Output a single integer, the maximum total value that can be obtained.

Source: adapted. Translated by ChatGPT 5