Hôm nay là sinh nhật Benjamin, thầy giáo Brogan tặng cậu ~3~ dãy số ~A~, ~B~ và ~C~. Dãy ~A~ có ~N~ phần tử còn dãy ~B~ và ~C~ thì có ~M~ phần tử. Từ dãy ~B~ và ~C~ ta thu được số ~K~ như sau:

~K = B_{1} ^ {C_{1}} \times B_{2}^{C_{2}} \times B_{3}^{C_{3}} \times B_{4}^{C_{4}} \times~ ...~\times B_{M}^{C_{M}}~

Dãy số ~B~ có tính chất là các phần tử khác nhau đôi một và mỗi phân tử là một số nguyên tố. Ngoài ra các phần tử trong dãy số ~A~, ~B~ và ~C~ đều là số nguyên dương. Benjamin sẽ nhận thêm một món quà với trị giá bằng số lượng dãy con liên tiếp đặc biệt của ~A~ mà Benjamin tìm được. Một dãy số được coi là đặc biệt nếu tích các phần tử của nó chia hết cho ~K~. Vì đây là các dãy số ngẫu nhiên mà thầy Brogan nghĩ ra nên thầy muốn biết giá trị phần thưởng lớn nhất là bao nhiêu để còn chuẩn bị quà cho Benjamin.

Input

• Dòng đầu chứa số ~N~ và ~M~.
• Dòng thứ hai chứa ~N~ số mô tả dãy ~A~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ~2~ số nguyên dương Bi và Ci.

Output

• Gồm một dòng chứa kết quả bài toán.

Giới hạn

• ~N~, ~M \le 10^{5}~.
• ~A_{i}~, ~B_{i}~, ~C_{i} \le 10^{9}~.
• ~30\%~ số test ~N \le 1000~.

Sample Input

4 2
1 2 3 4
2 1
3 1

Sample Output

5