#216926. [NWERC 2018] Fastest Speedrun

The classic video game “Prince of Python” comprises levels, numbered from to . 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 magical items. In the beginning you only have item 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 (), the number of levels.
• lines, describing the levels. The th line starts with two integers and (, ). The remainder has integers (), where is the completion time for level when playing by the rules using item .

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

样例输入 1

3
1 1 40 30 20 10
3 1 95 95 95 10
2 1 95 50 30 20

样例输出 1

91

样例输入 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

样例输出 2

17