Problem F
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. For example, on finishing level $5$, you obtain a mighty Gauntlet of 5 Fingers you may equip thereafter instead of the less-acclaimed Sword of 0 Damage you always start out with.
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?
Input
The input consists of:
-
One line containing an integer $n$ ($1 \le n \le 2\, 500$), the number of levels.
-
$n$ lines, describing the levels.
The $i$th such 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 remainder 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 using item $j$.
Output
Output the minimum time it takes to beat, in any order, all of the levels in the game.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 1 40 30 20 10 3 1 95 95 95 10 2 1 95 50 30 20 |
91 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 4 4 5 5 5 5 5 4 4 5 5 5 5 5 4 4 5 5 5 5 5 4 4 5 5 5 5 5 |
17 |
