Problem 1071 --成語接龍

1071: 成語接龍

Time Limit: 1 Sec  Memory Limit: 32 MB
Submit: 3  Solved: 3
[Submit][Status][Web Board]

Description

小明在玩成語接龍的遊戲。成語接龍的規則是,如果成語A的最後一個漢字與成語B的第一個漢字相同,那麼成語B就可以接到成語A的後面。
小明現在手上有一本成語詞典,每次他都得花費一定時間來從當前的成語查到下一個可以接在後面的成語。
現在給你一個成語列表,請你計算從列表中的第一個成語開始,到接到列表中的最後一個成語最少需要多長時間。

Input

輸入包含多組測試數據。
每組輸入第一行是一個整數N(0<N<1000),表示成語列表的長度。
接下來N行,每行先輸入一個整數T,再輸入一個字符串S。
S表示一條成語,T表示小明從S查到下一個成語所花費的時間。
每條成語由至少3個漢字組成,每個漢字由4個十六進制數(0~9和A~F)組成。
當N=0時,輸入結束。

Output

對於每組輸入,輸出從列表中的第一個成語開始,到接到列表中的最後一個成語需要的最少時間。
如果無法連接到列表中的最後一個成語,則輸出-1。

Sample Input

5
5 12345978ABCD2341
5 23415608ACBD3412
7 34125678AEFD4123
15 23415673ACC34123
4 41235673FBCD2156
2
20 12345678ABCD
30 DCBF5432167D
0

Sample Output

17
-1

HINT

Source

[Submit][Status]