P4138 [JOISC 2014] Straps

JOI-kun has $N$ ornaments, numbered $1, 2, \cdots, N$. He can attach some of them to his phone. Some ornaments are special—they have hooks that can hold other ornaments. Each ornament is either attached directly to the phone or to a hook of another ornament. At most one ornament can be attached directly to the phone. Each ornament has an integer joy value gained when it is installed. If JOI-kun dislikes an ornament, its joy value is negative. JOI-kun wants to maximize the sum of the joy values of all ornaments connected to the phone. It is not necessary to use all hooks, and attaching none is also allowed.

The first line contains an integer $N$, the number of ornaments. The next $N$ lines, the $i$-th line ($1 \le i \le N$), contain two space-separated integers $A_i$ and $B_i$, meaning ornament $i$ has $A_i$ hooks and yields joy $B_i$ when installed.

Output a single integer, the maximum total joy value of the ornaments connected to the phone.

- $1 \leq N \leq 2000$. - $0 \leq A_i \leq N$ ($1 \leq i \leq N$). - $-10^6 \leq B_i \leq 10^6$ ($1 \leq i \leq N$). Translated by ChatGPT 5