Description

小明在玩成语接龙的游戏。成语接龙的规则是，如果成语A的最后一个汉字与成语B的第一个汉字相同，那么成语B就可以接到成语A的后面。

小明现在手上有一本成语词典，每次他都得花费一定时间来从当前的成语查到下一个可以接在后面的成语。

现在给你一个成语列表，请你计算从列表中的第一个成语开始，到接到列表中的最后一个成语最少需要多长时间。

Format

Input

输入包含多组测试数据。

每组输入第一行是一个整数N（0<N<1000），表示成语列表的长度。

接下来N行，每行先输入一个整数T，再输入一个字符串S。

S表示一条成语，T表示小明从S查到下一个成语所花费的时间。

每条成语由至少3个汉字组成，每个汉字由4个十六进制数（0~9和A~F）组成。

当N=0时，输入结束。

Output

对于每组输入，输出从列表中的第一个成语开始，到接到列表中的最后一个成语需要的最少时间。

如果无法连接到列表中的最后一个成语，则输出-1。

Samples

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

17
-1

Limitation

1s, 1024KiB for each test case.