BUYCAN - Mua kẹo
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

Sau khi đạt giải cao trong kì thi HSG quốc gia, Tuấn với bản tính hào phóng của mình muốn mua bánh kẹo đãi các bạn trong lớp. Lúc này, Công ty TNHH Truyền thong giáo dục và Giải trí Phan Thị vừa ra mắt sản phẩm đặc biệt “kẹo Alocos” với chương trình khuyến mãi vô cùng hấp dẫn.

Với mỗi 3 vỏ kẹo Alocos khác nhau bạn sẽ nhận được một lá phiếu đổi thưởng bậc 1  và mỗi 3 lá phiếu đổi thưởng bậc k thì bạn sẽ nhận được 1 lá phiếu đổi thưởng bậc k+1 ( khi đổi vỏ hoặc phiếu đổi thưởng bạn không bị mất vỏ hoặc phiếu nào cả nhưng mỗi vỏ hoặc phiếu bạn chỉ có thể đổi được duy nhất 1 lần). Khách hàng có thể dùng những vỏ kẹo và phiếu đổi thưởng này để đổi những phần quá giá trị.

Tuấn có n đồng quyết định dùng tất cả số tiền này để mua kẹo cho các bạn và dùng số vỏ và phiếu nhận được để đi đổi thưởng. Hiện tại, trên địa bàn Đà nẵng hiện có m cửa hang bán kẹo Alocos, cửa hàng thứ i  (1<=i<=m)  bán một viên kẹo Alocos với giá ai đồng (tất cả cửa hàng đều có đủ số kẹo mà Tuần cần mua ) . Sau khi nhận được vỏ kẹo từ các bạn, Tuấn cùng người chị em kết nghĩa Tuyết Ni đi đến cửa hàng để đổi thường. Trớ trêu thay khi đến của hàng  thì Ni thấy rất thích thú với những món quà trong cửa hàng nên Tuấn quyết đinh tặng cho Ni x vỏ và phiếu đổi thưởng. Biết x bằng số mũ của 3 sau khi phân thích N! thành thừa số nguyên tố (N chính là số kẹo mà Tuấn mua)

Bạn hãy tính số vỏ và phiếu đổi thưởng còn lại tối đa của Tuấn.

Input

Dòng 1 gồm 2 số nguyên dương n (n<=1018)  và m (m<=2 * 105) – là số đồng Tuấn có và số cửa hàng
Dòng 2 gồm m số nguyên dương  ai(1<=i<=m)

Output

Ghi ra một số nguyên duy nhất là tổng số vỏ và phiếu đổi thưởng còn lại tối đa của Tuấn.

Ví dụ

Input

12  4
3  5  6  4

Output

4

Giải thích

Với 12 đồng mua ở cửa hàng thứ nhất được N=4 viên kẹo và Tuấn nhận được tổng cộng 4 vỏ kẹo + 1 phiếu đổi thưởng bậc 1 = 5
N!=1*2*3*4=2^3*3^1 => x=1

Tổng số vỏ+phiếu là 5-1=4


Nguồn: Duy-Ngọc-Tuấn

Back to Top