题目背景

市科技馆准备在周末开放一套环形轨道互动装置。轨道边缘被划分成若干格，其中一部分格子已经完成巡检并贴上了标记。

工程师林澈负责调试装置，志愿者小悠则使用若干枚不同颜色的磁性棋子继续巡检。控制器只允许棋子按给定的几种步数顺时针前进。棋子到达一个尚未标记的格子时，就会停在那里并留下标记；当它绕行后回到自己的出发格时，这枚棋子的任务便完成，可以从轨道上取下。

已经标记过的格子不能被其他巡检路线重复使用。为了减少同时准备的棋子数量，林澈想知道：至少需要放置多少枚棋子，才能把整条环形轨道全部巡检完毕。

题目描述

有一个由 $n$ 个格子组成的环形轨道，所有格子按顺时针方向排列。第 $n$ 个格子与第 $1$ 个格子相邻。

字符串 markedSquares 描述轨道的初始状态：

• X 表示该格子已经被标记；
• . 表示该格子尚未被标记。

开始游戏时，你可以选择若干个互不相同的未标记格子，并在每个选中的格子上放置一枚颜色各不相同的棋子。每枚棋子所在的起始格会立即被标记。

之后可以反复进行如下操作：

1. 选择一枚仍在轨道上的棋子；
2. 从数组 allowedMoves 中选择一个整数 $d$；
3. 将该棋子沿顺时针方向前进 $d$ 个格子。

棋子落下后，按以下规则处理：

• 若落点尚未被标记，则棋子停留在该格，并将该格标记；
• 若落点恰好是这枚棋子自己的起始格，则将该棋子从轨道上取下；
• 否则，若落点已经被标记，则本次移动无效，棋子回到移动前的位置。

当且仅当所有格子都已经被标记，并且所有棋子都至少移动过一次、最终回到各自的起始格后被取下，称为完成了轨道。

请计算完成轨道所需的最少棋子数量。若无论如何都无法完成，输出 -1。

输入格式

第一行输入一个整数 $m$，表示允许的移动步数数量。

第二行输入 $m$ 个互不相同的整数 $a_1,a_2,\ldots,a_m$，表示数组 allowedMoves。

第三行输入一个仅由 X 和 . 组成的字符串 markedSquares，描述环形轨道的初始状态。

输出格式

输出一个整数，表示完成轨道所需的最少棋子数量。

若无法完成，输出 -1。

样例 1

输入

1
4
............

输出

4

说明

轨道共有 $12$ 个格子，棋子每次只能前进 $4$ 格。每枚棋子会在三个位置之间循环，因此在连续四个格子上各放置一枚棋子即可覆盖全部格子。

样例 2

输入

1
4
.............

输出

1

说明

轨道共有 $13$ 个格子。不断前进 $4$ 格会依次经过全部格子，最终回到起点，因此一枚棋子即可完成。

样例 3

输入

3
6 5 4
..X.X..XX...X.X...XX..X.X

输出

2

样例 4

输入

3
5 3 2
.XX....XX..XX....XX..XX.

输出

1

样例 5

输入

3
6 4 1
..XXX..XXX..XXX

输出

1

样例 6

输入

2
2 3
..X..XX.X...XX

输出

-1

说明

不存在能够覆盖全部未标记格子并让所有棋子回到各自起点的方案。

数据范围

• $6\le |\texttt{markedSquares}|\le 50$；
• markedSquares 中每个字符均为 X 或 .；
• markedSquares 中至少包含一个 .；
• $1\le m\le 6$；
• $1\le a_i\le 6$；
• 所有 $a_i$ 互不相同。