电话线路

时间限制:10s      空间限制:128MB

题目描述

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建立通信联系?


输入格式


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


输出格式

 

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


样例输入

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


样例输出

211



提示

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


题目来源

Poetize7