题目描述

在一个电子游戏中，玩家需要从屏幕底部一路跳到屏幕顶部。屏幕中间有若干排会水平移动的悬浮平台。玩家只能站在平台上；如果跳到没有平台的位置，游戏立即失败；如果玩家当前所在的平台格子随着平台移动出了屏幕边界，游戏也立即失败。

屏幕宽度固定为 $20$ 个单位格，每个格子大小为 $1\times1$。屏幕最下方和最上方各有一整排静止的实心地面，它们没有空洞，也不会移动。玩家最开始位于最下方地面的最左侧格子。

每一排移动平台由一个长度为 $5$ 的字符串模式描述，其中 # 表示平台，. 表示空位。在初始时刻，这个长度为 $5$ 的模式会重复 $4$ 次，从而铺满宽度为 $20$ 的整行。例如模式 #..## 对应的初始一行为：

#..###..###..###..##

每种模式还对应一个非零整数速度。正数表示向右移动，负数表示向左移动，绝对值表示每秒移动的格数。平台从屏幕一侧移出后，会按照相同的周期模式从另一侧补入。例如上面的模式若速度为 $3$，移动一秒后该行变为：

.###..###..###..###.

需要特别注意：虽然新的平台会从另一侧补入，但如果玩家所在的那个平台格子在移动过程中越过了屏幕左右边界，玩家仍然会失败。

设中间共有若干排移动平台。字符串 rows 描述每一排使用哪一种模式和速度：rows 中较靠前的字符表示更靠近屏幕底部的行，字符数字 $d$ 表示该行使用第 $d$ 种模式及其对应速度。模式编号从 $0$ 开始。

每一秒开始时，玩家可以执行以下五种操作之一：

• 原地不动；
• 向左移动一格；
• 向右移动一格；
• 向上一行移动一格；
• 向下一行移动一格。

玩家一次只能移动一个单位格，并且跳跃本身不消耗额外时间。在玩家完成本秒的移动后，所有移动平台立即按照各自速度移动一秒；如果玩家此时站在某个移动平台上，他会被该平台一起带动。

玩家可以在最下方的实心地面上等待、左右移动，也可以在跳上平台后重新跳回最下方地面。当玩家从最后一排移动平台跳到最上方的实心地面时获胜。

请计算玩家从初始位置到达屏幕顶部所需的最少时间。如果无论如何都无法到达，输出 $-1$。

输入格式

第一行输入一个整数 $P$，表示平台模式的数量。

接下来 $P$ 行，每行输入一个长度为 $5$ 的字符串，依次表示第 $0$ 到第 $P-1$ 种平台模式。字符串只包含 # 和 .。

接下来一行输入一个整数 $S$，表示速度数组的长度。保证 $S=P$。

下一行输入 $S$ 个整数，第 $i$ 个整数表示第 $i$ 种平台模式对应的水平速度。

最后一行输入字符串 rows，其中第 $i$ 个字符表示从下往上第 $i+1$ 排移动平台所使用的模式编号。

输出格式

输出一个整数，表示玩家到达屏幕顶部所需的最少时间；如果无法到达，输出 $-1$。

数据范围与约定

• $1\le P=S\le4$；
• 每个模式字符串长度均为 $5$，且只包含 # 和 .；
• 每个速度均满足 $-10\le v_i\le10$ 且 $v_i\ne0$；
• $2\le |\text{rows}|\le20$；
• rows 中每个字符均为 0 到 '0'+P-1 之间的数字字符；
• 屏幕宽度恒为 $20$。

输入输出样例 #1

输入

2
###..
..###
2
1 1
01

输出

5

输入输出样例 #2

输入

2
###..
..###
2
5 5
01

输出

5

输入输出样例 #3

输入

2
....#
....#
2
4 5
0111

输出

9

样例说明

在样例 #3 中，玩家必须先等待第一排平台移动到最左列附近。等待 $4$ 秒后，再连续向上移动 $5$ 次即可到达顶部，因此最少需要 $9$ 秒。