Description

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.

Input Format

• 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 Format

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

50 
5 0 10 1 10 1 5 0 10 2 500 1 1000 2 18 1 1000000 4 

1500

Hint

Source: adapted.

Translated by ChatGPT 5