P1270 "Visiting" the Art Museum

After months of meticulous preparation, Peer Brelstet, a notorious art thief, is ready for his next move. The art museum is structured so that each corridor either splits into two corridors or leads to an exhibition room. Peer knows how many paintings are hidden in each room, and he has measured precisely the time to traverse each corridor. Since he is experienced, taking one painting takes $ 5 $ seconds. Your task is to write a program to compute the maximum number of paintings he can steal before the police arrive. Assume that after returning to the starting point, he still has at least $ 1 $ second left to escape. 

The first line is the time when the police arrive, in seconds. The second line describes the structure of the art museum as a sequence of non-negative integers given in pairs: in each pair, the first number is the time to traverse a corridor, and the second number is the number of paintings at its end; if the second number is $ 0 $, it means this corridor branches into two other corridors. The data are given in depth-first order; see the sample. A room contains at most $ 20 $ paintings. The time to traverse any corridor does not exceed $ 20 $ seconds. The art museum has at most $ 100 $ rooms. The police arrival time is no more than $ 6000 $ seconds.

Output the maximum number of paintings he can steal.

Translated by ChatGPT 5