P4042 [AHOI2014/JSOI2014] Knight Game

In his long homebody life, JYY dug up an RPG game. In this game, JYY plays a brave knight who uses his longsword to kill monsters invading the village.

In this game, JYY has two attack types: a normal attack and a spell attack. Both consume some of JYY’s stamina. Using a normal attack on a monster does not completely kill it; the monster’s corpse can transform into some new monsters. Note that after several normal attacks, a monster may turn into one or more monsters of the same type again. A spell attack, however, can permanently kill a monster. Of course, in general, compared with a normal attack, a spell attack consumes more stamina (but due to a game system bug, this is not guaranteed). There are $N$ different kinds of monsters in the game world, numbered from $1$ to $N$. Now a monster of type $1$ has invaded the village. JYY wants to know the minimum stamina needed to kill all monsters in the village.

The first line contains an integer $N$. Then $N$ lines follow, each describing one monster type. The $i$-th line contains several integers. The first three integers are $S_i$, $K_i$, and $R_i$, meaning: for monster type $i$, a normal attack costs $S_i$ stamina, a spell attack costs $K_i$ stamina, and after monster $i$ dies (by a normal attack), it spawns $R_i$ new monsters. After these three integers, there are exactly $R_i$ more integers, each giving the type number of one newly spawned monster. The same type number may appear multiple times.

Output one integer on a single line: the minimum stamina required.

First use a normal attack costing $4$ stamina, and the spawned monster types are $2$, $2$, and $3$. Spend $10$ stamina using spell attacks to kill the two monsters of type $2$. For the remaining type $3$ monster, use a normal attack costing $1$ stamina. Now the monsters in the village are of types $2$ and $4$. Finally, spend $11$ stamina using spell attacks to permanently kill these two monsters. The total stamina spent is $4 + 5 + 5 + 1 + 5 + 6 = 26$. Constraints: For all testdata, $2 \le N \le 2 \times 10^5$, $1 \le R_i, \sum R_i \le 10^6$, $1 \le K_i, S_i \le 5 \times 10^{14}$. Translated by ChatGPT 5