406675: GYM102483 F Fastest Speedrun

Memory Limit:256 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Fastest Speedruntime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

ExamplesInput
3
1 1 40 30 20 10
3 1 95 95 95 10
2 1 95 50 30 20
Output
91
Input
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
Output
17

加入题单

上一题 下一题 算法标签: