Vào ngày sinh nhật của LQDOJ, shiba - một thành viên của Team Shiba quyết định tặng kẹo cho các bạn trẻ trong trường. Có \(N\) đứa trẻ muốn được nhận kẹo và shiba có một bịch kẹo gồm \(M\) vị khác nhau. Có một điều khiến shiba phải băn khoăn rằng tất cả đứa trẻ muốn tất cả viên kẹo mà mình có đều phải có cùng một vị. shiba cũng biết rằng các bạn trẻ sẽ ghen tị nếu có một bạn được quá nhiều kẹo. Để giải quyết các điều này một cách êm đềm nhất, shiba quyết định chia kẹo sao cho mức độ ghen tị sẽ là nhỏ nhất có thể, biết rằng mức độ ghen tị là số kẹo nhiều nhất mà một bạn trẻ có được.

Ví dụ bịch kẹo của shiba có \(7\) viên kẹo vị \(X\) và \(4\) viên kẹo vị \(Y\) thì mà cần chia cho \(5\) đứa trẻ thì shiba có thể chia như sau: \(XX\),\(XX\),\(YY\),\(YY\),\(YYY\). Mức độ ghen tị lúc này là \(3\), là mức độ ghen tị nhỏ nhất có thể.

Tuy nhiên thực hiện việc chia kẹo là quá khó với shiba. Anh ấy nhờ các bạn lập trình tài năng của LQDOJ giúp shiba tìm cách chia sao cho mức độ ghen tị là nhỏ nhất có thể.

Yêu cầu: Bạn hãy giúp shiba tính mức độ ghen tị nhỏ nhất có thể. Biết rằng trường hợp có đứa trẻ không nhận được một viên kẹo nào là có thể xảy ra.

Input

• Dòng đầu tiên chứa hai số nguyên dương lần lượt là \(N\) và \(M\) \((1 \le N \le 10^9,1 \le M \le 3 \times 10^5, M \le N)\).
• \(M\) dòng tiếp theo mỗi dòng chứa một số nguyên dương là số kẹo của từng vị mà shiba có. Số kẹo của từng vị nằm trong đoạn \([1;10^9]\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Có \(N \le 25\).
• Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 2
4
7

3