Vì ITK20 & ITK21 đạt thành tích cao tại kỳ thi Vở sạch chữ đẹp diễn ra vừa qua do sở GD Quảng Nam tổ chức, __BruteForce__ quyết định sẽ tặng kẹo cho các em học sinh của hai lớp.

Hai lớp có tổng cộng \(N\) học sinh và có \(M\) loại kẹo khác nhau. __BruteForce__ muốn chia hết tất cả số lượng kẹo cho học sinh. Một em học sinh bất kỳ trong lớp có thể không được tặng viên nào nhưng nếu được tặng thì tất cả các viên kẹo nhận được phải cùng loại với nhau.

Dù là bạn cùng lớp rất thân thiết nhưng các em vẫn sẽ đố kỵ nhau nếu có một bạn nào đó nhận được quá nhiều kẹo, do đó cần cực tiểu hóa mức độ đố kỵ này. Mức độ đố kỵ chính bằng với số lượng viên kẹo của em học sinh nhận được nhiều kẹo nhất. Hãy giúp __BruteForce__ tìm cách chia kẹo để cực tiểu hóa mức độ đố kỵ nhé!

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(M\ (N\leq10^9,\ M\leq3\times10^5,\ M\leq N)\) - lần lượt là số lượng học sinh và số loại kẹo khác nhau;
• Tiếp sau đó là \(M\) dòng, dòng thứ \(i\) là số nguyên dương \(a_i\) thể hiện số lượng viên kẹo của loại thứ \(i\) mà __BruteForce__ có.

Output

• In ra một số nguyên dương duy nhất là mức độ đố kỵ nhỏ nhất có thể.

Ví dụ

Sample input 1

3 2
2
1

Sample output 1

1

Sample input 2

7 5
7
1
7
4
4

Sample output 2

4