THPT Chuyên Bến Tre

Cô giáo có một số viên bi, mỗi viên bi có một màu sắc có mã màu thuộc đoạn [1, M], cần chia cho N đứa trẻ. Nếu số bi quá ít, số trẻ quá nhiều thì sẽ có một vài trẻ không có viên bi nào, và cách chia đó cũng có thể chấp nhận được. Việc phân chia phải thỏa mãn điều kiện: tất cả những viên bi mà trẻ nhận được phải cùng một màu sắc.

Cô giáo cũng biết rằng trẻ em sẽ ghen tị nếu một đứa trẻ nhận quá nhiều bi. Mức độ ghen tị của cả nhóm là số lượng viên bi lớn nhất được trao cho một đứa trẻ.

Hãy giúp cô chia các viên bi sao cho mức độ ghen tị của cả nhóm là nhỏ nhất có thể.

Ví dụ: Có 4 viên bi đỏ (RRRR) và 7 viên bi xanh (BBBBBBB), cần chia cho 5 trẻ thì cách chia: RR, RR, BB, BB, BBB cho ta mức độ ghen tị bằng 3, và đây là cách chia tối ưu.

Input

• Dòng 1 chứa 2 số nguyên N (1 ≤ N ≤ 10⁹) - số lượng trẻ, và M (1 ≤ M ≤ 30000, M ≤ N) – số lượng màu.
• M dòng tiếp theo, dòng thứ K là một số nguyên S (1 ≤ S ≤ 10⁹) thể thiện có S viên bi màu K.

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Example

Input:
7 5
7
1
7
4
4

Output:
4