Rescue the Princess

Billy has ventured into the demon's castle to save his beloved Princess Julie. The final door to the Demon Palace is located at position n+1, while Billy starts at position 0. Between these two points lies a narrow corridor with n dangerous cells numbered 1 through n. At each unit of time, Billy may choose to move one cell left, one cell right, or remain in place.

However, above each cell i (1 \leq i \leq n), storms of falling stones inflict damage in a periodic pattern. The period for cell i is given by a positive integer c_i. The pattern is described by c_i integers: $$h_1, h_2, \cdots, h_{c_i},$$ which means that if Billy is at cell i at time $$t = k\cdot c_i + x \quad (1 \le x \le c_i),$$ he will suffer h_x units of damage. (Note that if h_x = 0, then no damage is incurred at that time.)

Note that cell 0 is safe and does not impose any damage. Billy is guaranteed to survive regardless of the damage taken. Your task is to compute the minimum total damage Billy suffers in order to reach the Demon Palace at position n+1.

Input/Output details: The input begins with an integer n indicating the number of dangerous cells. Then n lines follow, each beginning with c_i followed by c_i integers representing the damage pattern for cell i. The output should be a single integer: the minimum total damage incurred along the route.

Movement details: In every time unit, Billy can move to an adjacent cell (left or right) or simply remain in his current cell. When moving into a dangerous cell (cells 1 to n), the damage he suffers is determined by the time at which he enters that cell. If he arrives at cell i at time t, the damage is calculated as follows:

$$\text{damage} = \begin{cases} h_{t \bmod c_i} &\text{if }t \bmod c_i \neq 0,\\ h_{c_i} &\text{if }t \bmod c_i = 0. \end{cases}$$

Cells 0 and n+1 are safe (impose 0 damage). Billy starts at cell 0 at time 0, and the first movement occurs at time 1.

inputFormat

The first line contains a single integer n (the number of dangerous cells).

The following n lines each describe a cell. Each line begins with an integer c_i (the period for cell i), followed by c_i space‐separated integers h₁, h₂, \dots, h_{c_i} representing the damage pattern for that cell.

outputFormat

Output a single integer, the minimum total damage Billy must suffer to reach the Demon Palace at position n+1.

sample

1
3 1 2 0

1