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。