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 thông 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 \leq i \leq m)\) bán một viên kẹo Alocos với giá \(a_i\) đồ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 tí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\ leq 10^{18})\) và \(m(m \leq 2 \times 10^5)\) – là số đồng Tuấn có và số cửa hàng
• Dòng 2 gồm m số nguyên dương \(a_i(1 \leq i \leq 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.

Example

12  4
3  5  6  4 

4