bzoj#P3045. 电话线路

电话线路

题目描述

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

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

另外,如果 a a b b 能通信,b b c c 能通信,那么 aacc 也能借助b来通信。a a c c 借助 b b 建立通信联系所用时间是 cost[lcp(a,b)]+cost[lcp(b,c)] cost[ {\rm lcp}(a,b) ]+ cost[ {\rm lcp}(b,c) ]

现在 Freda 想给 Rainbow 打电话,请你告诉 Freda,她最快需要多少时间才能与与 Rainbow 建立通信联系?

输入格式

第一行一个整数 n n ,表示电话号码的个数。

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

接下来 n n 行每行一个整数表示电话号码。第一个是 Freda 的电话号码,第 nn 个是 Rainbow 的电话号码。

输出格式

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

样例输入

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

样例输出

211

数据规模与约定

对于100%的数据,保证 2n5×104 2\leq n\leq 5\times 10^4 ,每个电话号码是一个独一无二的十位十进制数字串, 1cost[1..10]1×103 1\leq cost[1..10]\leq 1\times 10^3

题目来源

Poetize7