Fastest Speedrun

The classic video game "Prince of Python" has $n$ levels, numbered from 1 to $n$. You want to speedrun the game by finishing all levels as fast as possible. You may beat the levels in any order.

You enter each level with one of $n + 1$ magical items. At the start, you only have item 0 in your inventory. When you beat a level, you keep the item with the same number as that level. For example, after finishing level 5, you obtain the Gauntlet of 5 Fingers, which you can equip from then on instead of the Sword of 0 Damage you start with.

The time to beat a level depends on the item you bring into it. Higher-numbered items are stronger, so when playing by the rules, using a higher-numbered item is never slower than using a lower-numbered one.

Each level also has a shortcut left in by the developers. The shortcut for a level is triggered by using one specific item in an unconventional way. Using the shortcut finishes the level in a time that is no greater than the time for any other item.

What is the minimum total time needed to beat all of the levels?

The input consists of:

• One line with an integer $n$ ($1 \le n \le 2500$), the number of levels.
• $n$ lines describing the levels.
  The $i$-th line starts with two integers $x_i$ and $s_i$ ($0 \le x_i \le n$, $1 \le s_i \le 10^9$), the shortcut item for level $i$ and the completion time for level $i$ when using the shortcut. The rest of the line has $n + 1$ integers $a_{i,0}, \ldots, a_{i,n}$ ($10^9 \ge a_{i,0} \ge a_{i,1} \ge \ldots \ge a_{i,n} \ge s_i$), where $a_{i,j}$ is the completion time for level $i$ when playing by the rules with item $j$.

Output the minimum time needed to beat all of the levels, in any order.