You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

2.老虎机（tiger）

时间显示：$1s$，空间限制：$256MB$

题目描述

​ 小Y有一个老虎机，老虎机上有$n$个玻璃框，每个玻璃框后环形排列着多个图案，以一个字符串表示，每次拉下拉杆，所有玻璃框后的图案会开始按同一方向转动。

​ 小Y找到了转动的规律，每次拉下拉杆之后，第$i$个玻璃框后的图案会转过$a_i$个图案，例如$abcd$转过3个图案会变为$dabc$。

​ 现在已知老虎机的初始情况，小Y想知道至少需要拉下多少次拉杆，老虎机中的元素可以转回初始的状态，即每个玻璃框后的图案序列均与初始时的序列相同。

输入格式

​ 输入文件名为$tiger.in$。

​ 输入文件的第一行包含两个正整数$n$，表示有$n$个玻璃框。

​ 接下来一行包含$n$个正整数，第$i$个正整数$a_i$表示每次拉下拉杆，第$i$个玻璃框后的图案会转过$a_i$个图案。

​ 接下来$n$行每行包含一个字符串，表示每个玻璃框后的图案序列。

输出格式

​ 输出文件名为$tiger.out$

​ 输出一个正整数，表示至少需要拉下多少次拉杆老虎机可以回到初始状态。

样例

样例1

输入数据：

2
3 6
abcabc
fzcsyglq

输出数据：

4

样例2

见选手目录下的tiger2.in和tiger2.ans

数据范围与约定

​ 对于$30\%$的数据，满足$n\le 5$，字符串长度$\le 5$。

​ 对于另$20\%$的数据，满足$a_i=1$。

​ 对于另$20\%$的数据，满足$n=1$。

​ 对于$100\%$的数据，满足$1\le n\le 10,\ 1\le a_i\le 10^9,\ 1\le 字符串长度\le 10^5$，保证只出现小写字母，最终答案不会超过$long\ long$的范围。