题目描述

Rainbow 和 Freda 终于走出了幻象迷宫，不过经历了汪星人的一场入侵，Freda 的城堡和 Rainbow 的城堡之间的电话线路出了故障，使得只有满足某种要求的两个电话号码之间才可以直接通信。

每台电话都有一个独一无二的号码，用一个十位的十进制数字串表示。电话 $a$ 和 $b$ 之间能直接通信，当且仅当“ $a$ 与 $b$ 之间仅有一个数字不同”，或者“交换 $a$ 的某两位上的数字后，$a$ 与 $b$ 相同”。而 $a$、$b$ 之间建立通信联系所需要的时间为 $cost[ {\rm lcp}(a,b) ]$ ，其中 ${\rm lcp}(a,b)$ 表示 $a$、$b$ 的最长公共前缀的长度，${\rm lcp}(a,b)$ 越大，通信时间越快，$cost$ 是个常数数组。

另外，如果 $a$、$b$ 能通信，$b$、$c$ 能通信，那么 $a$、$c$ 也能借助b来通信。$a$、$c$ 借助 $b$ 建立通信联系所用时间是 $cost[ {\rm lcp}(a,b) ]+ cost[ {\rm 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\leq n\leq 5\times 10^4$，每个电话号码是一个独一无二的十位十进制数字串， $1\leq cost[1..10]\leq 1\times 10^3$。

题目来源

Poetize7