eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Multi Path Story

Multi Path Story

Ліміт часу 5 секунд
Ліміт використання пам'яті 256 MiB

You are a programmer who loves pretty girl games (a sub-genre of dating simulation games). A game, which is titled "Floatable Heart" and was released last Friday, has arrived at your home just now. This game has multiple stories. When you complete all of those stories, you can get a special figure of the main heroine, Megumi. So, you want to hurry to play the game! But, let's calm down a bit and think how to complete all of the stories in the shortest time first.

In fact, you have the special skill that allows you to know the structure of branching points of games. By using the skill, you have found out that there are n branching points in this game and i-th branching point has k_i choices. This game is so complicated that multiple routes get to i-th branching point probably. You also noticed that it takes c_{ij }minutes to proceed from i-th branching point to another branching point (or an ending), if you select j-th choice of i-th branching point. Of course you need to select all the choices on all the branching points and read stories between a branching point and another branching point (or an ending) to complete all of those stories. In addition, you can assume it only takes negligible time to return to the beginning of the game ("reset") and to play from the beginning to the first branching point.

The game’s manual says that this game has an additional feature called "Quick Save”, and the feature allows you to record the point where you are currently playing and return there at any time later. However, this feature is not working for some bug. Thus you have to restart from the first branching point every time, if you reach an ending or quit the game on the way. Any patch to fix this bug has not been yet published. This is an imposed tribulation for the fastest players.

Well, let's estimate how long it will take for completing all of the stories in the shortest time.

Вхідні дані

A data set is given in the following format.

n

k_1 t_11 c_12 ... t_1k1 c_1k1

...

k_n t_n1 c_n2 ... t_nkn c_nkn

The first line of the data set contains one integer n (2n1000), which denotes the number of the branching points in this game. The following n lines describe the branching points. The i-th line describes the branching point of ID number i. The first integer k_i (0k_i50) is the number of choices at the i-th branching point. k_i0 means that the i-th branching point is an ending. Next 2k_i integers t_ij (1t_ijn) and c_ij (0c_ij300) are the information of choices. t_ij denotes the ID numbers of the next branching points when you select the j-th choice. c_ij denotes the time to read the story between the i-th branching point and the t_ij-th branching point. The branching point with ID 1 is the first branching point. You may assume all the branching point and endings are reachable from the first branching point. You may also assume that there is no loop in the game, that is, no branching point can be reached more than once without a reset.

Вихідні дані

Print the shortest time in a line.

Приклад

Вхідні дані #1
2
1 2 2
0
Вихідні дані #1
2
Джерело Japan Alumni Group Summer Camp 2013 Day 4, 2013/09/23