P16989 [NWERC 2018] Fastest Speedrun

The classic video game “Prince of Python” comprises $n$ levels, numbered from $1$ to $n$. You are going to speedrun this game by finishing all of the levels as fast as possible, and you can beat them in any order that you want. You enter each level equipped with one of $n+1$ magical items. In the beginning you only have item $0$ in your inventory. Once you beat a level, you get to keep the item numbered the same as that level. Beating a level can take different amounts of time depending on which item you take into the level with you. Higher-numbered items are more powerful, so if playing by the rules it is always at least as fast to finish the level with a higher-numbered item as with a lower-numbered item. However, each level also has a shortcut left in by the developers. The shortcut for a level can be accessed by applying a specific item in an unconventional way. By doing so you can finish the level as fast as, or even faster than, if you had used any of the other items. How long will it take you to beat all of the levels of the game?

The input consists of: - One line containing 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 remainder has $n+1$ integers $a_{i,0},\ldots,a_{i,n}$ ($10^9\ge a_{i,0}\ge\cdots\ge a_{i,n}\ge s_i$), where $a_{i,j}$ is the completion time for level $i$ when playing by the rules using item $j$.

Output the minimum time it takes to beat, in any order, all of the levels in the game.