수족관의 공통 먹이 봉투

문제

한 수족관에서는 수조마다 하루에 사용할 먹이 알갱이를 미리 세어 보관한다. 오늘 준비해야 하는 수조는 N개이며, i번 수조에는 정확히 A_i개의 알갱이를 배정했다. 관리자는 배정된 양을 바꾸지 않으면서 먹이를 여러 봉투에 나누어 담으려 한다. 봉투를 쉽게 구별하고 포장 작업을 단순하게 만들기 위해 모든 수조에서 같은 크기의 봉투를 사용하기로 했다. 봉투 크기 K는 봉투 하나에 넣는 알갱이의 개수이며 양의 정수다. 사용하는 모든 봉투에는 정확히 K개의 알갱이를 넣어야 한다. 일부만 채운 봉투는 허용하지 않고, 수조에 배정된 알갱이를 남기는 것도 허용하지 않는다. 또한 서로 다른 수조의 알갱이를 합쳐 하나의 봉투에 넣거나, 어느 수조의 알갱이를 다른 수조로 옮길 수 없다. 따라서 각 수조에 배정된 양을 그 수조의 봉투만으로 정확하게 포장해야 한다. 예를 들어 어느 수조에 20개의 알갱이가 배정되었다면 크기 4인 봉투 다섯 개로 포장할 수 있다. 반면 크기 6인 봉투로는 일부 알갱이가 남으므로 그 수조의 포장 조건을 만족하지 못한다. 한 수조를 포장할 수 있다는 사실만으로 충분하지 않으며, 선택한 K가 모든 수조에서 동시에 사용 가능해야 한다. 수족관이 보유한 포장 장비에는 봉투 크기의 하한 L과 상한 R도 정해져 있다. 선택한 크기는 L 이상 R 이하이어야 하며 양 끝값도 선택할 수 있다. 관리자는 조건을 만족하는 크기 중 가장 큰 것을 사용하려 한다. 같은 크기를 사용한다면 수조마다 필요한 봉투 수는 달라도 되며, 봉투 수에는 별도의 제한이 없다. 모든 수조의 알갱이를 규칙에 맞게 포장하면서 장비의 범위도 만족하는 가장 큰 봉투 크기를 구해야 한다. 가능한 크기가 하나도 없다면 0을 출력한다. 출력하는 값은 필요한 봉투 수의 합이 아니라 봉투 하나에 들어가는 알갱이의 개수다.

입력

첫째 줄에 정수 N, L, R이 공백으로 구분되어 주어진다. 1 ≤ N ≤ 30,000, 1 ≤ L ≤ R ≤ 1,000,000,000이다.
둘째 줄에 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 i에 대해 1 ≤ A_i ≤ 1,000,000,000이다.

출력

조건을 만족하는 가장 큰 봉투 크기를 정수로 한 줄에 출력한다. 가능한 크기가 없다면 0을 출력한다.

4 4 10
24 36 60 84

6

3 7 10
18 30 42

0

1 10 20
36

18

출처: Devin.KR 자체 제작