Cho số nguyên dương ~n~ và ~k~ số nguyên tố phân biệt ~a_1,a_2,\ldots,a_k~.

Yêu cầu

Đếm trong các số tự nhiên từ ~1~ đến ~n~ có bao nhiêu số chia hết cho ít nhất một trong ~k~ số nguyên tố đã cho.

Input

Dòng đầu chứa hai số nguyên ~n,k~ ~(1 \le n \le 10^{18}, 1 \le k \le 20)~.

Dòng thứ hai chứa ~k~ số nguyên tố phân biệt ~a_i~ ~(2 \le a_i \le 10^{18})~.

Output

In ra số lượng số tìm được. Nếu không có số nào, in -1.

Subtask

• 100% số điểm: ~1 \le n \le 10^{18}~, ~1 \le k \le 20~.

Ví dụ

20 2
2 5

12