#479. 电话线路

电话线路

Description

Rainbow和Freda终于走出了幻象迷宫,不过经历了汪星人的一场入侵,Freda的城堡和Rainbow的城堡之间的电话线路出了故障,使得只有满足某种要求的两个电话号码之间才可以直接通信。 每台电话都有一个独一无二的号码,用一个十位的十进制数字串表示。电话a和b之间能直接通信,当且仅当“a与b之间仅有一个数字不同”,或者“交换a的某两位上的数字后,a与b相同”。而a、b之间建立通信联系所需要的时间为cost[ lcp(a,b) ],其中lcp(a,b)表示a、b的最长公共前缀的长度,lcp(a,b)越大,通信时间越快,cost[]是个常数数组。 另外,如果a、b能通信,b、c能通信,那么a、c也能借助b来通信。a、c借助b建立通信联系所用时间是cost[ lcp(a,b) ]+ cost[ lcp(b,c) ]。 现在Freda想给Rainbow打电话,请你告诉Freda,她最快需要多少时间才能与与Rainbow建立通信联系?

Format

Input

第一行一个整数N,表示电话号码的个数。 第二行10个整数,第i个整数表示cost[i-1],即当两个能够直接通信的号码的最长公共前缀为i-1时,二者之间建立通信联系所需的时间。 接下来N行每行一个整数表示电话号码。第一个是Freda的电话号码,第N个是Rainbow的电话号码。

Output

一个整数,表示所求时间。若Freda和Rainbow不能建立通信联系,输出-1。

Samples

5
100 10 10 10 1 1 1 1 1 1
9123493342
3123493942
9223433942
3223493942
9223433945
211

Limitation

对于 100% 的数据,保证2<=N<=50000,每个电话号码是一个独一无二的十位十进制数字串,1<=cost[1..10]<=1000。