P2334 [SCOI2006] Castle

To rescue his beloved princess Julie, Billy has arrived at the demon’s castle. After fighting for three days and nights, the Demon King’s hall is within reach. This is a narrow corridor. Billy is at position $0$, and the Demon King’s hall is at position $n + 1$. At each unit of time, Billy may move one unit left, one unit right, or stay in place. Above each cell, stones periodically fall; the period of cell $i$ is $c_i$. For the stones above cell $i$, we use $c_i$ integers $h_1, h_2, \cdots, h_{c_i}$ to describe them: at time $t = k c_i + x$ ($1 \le x \le c_i$) for any integer $k \ge 0$, being on that cell will cause a loss of $h_x$ HP. Here $h_x = 0$ means no stone falls at that moment. Compute the minimum total HP that Billy must lose to reach the Demon King’s hall. Assume Billy will not die. Note that from position $1$ you may move back to position $0$, and at position $0$ no HP is lost.

The first line contains an integer $n$, the length of the corridor. The next $n$ lines describe cells $1, 2, \cdots, n$. In each line, the first integer is $c_i$, the falling period, followed by $c_i$ integers $h_1, h_2, \cdots, h_{c_i}$.

Output a single integer HP, the minimum total HP lost.

- For $50\%$ of the testdata, $n \le 20$. - For $100\%$ of the testdata: $0 \le n \le 1000$, $1 \le c_i \le 10$, $0 \le h_x \le 100$. - 2023-04-12: Added one hack testdata (not scored). Translated by ChatGPT 5