주기 매미

북아메리카의 주기 매미는 알려진 곤충 중에서 생애 주기가 가장 길다. 17년마다 성충이 되어 짝짓기를 하고 알을 낳은 뒤 죽는다. 새로 태어난 애벌레는 땅속 20센티미터 깊이로 숨어들어 17년 동안 뿌리의 수액을 먹고 자라다가, 자기 차례가 오면 땅 위로 나온다.

이 17이라는 숫자는 우연이 아니라고 본다. 같은 지역의 다른 매미 종은 13년 주기여서 두 종이 같은 해에 나오는 일은 221년에 한 번뿐이다. 덕분에 두 종이 섞일 가능성이 크게 줄고, 한쪽 개체군의 형질이 다른 쪽으로 들어가지 않는다.

이 현상에서 착안한 진화 알고리즘이 있다. 마지막 단계에서 가장 좋은 해 후보를 여러 개체군으로 나누고, 개체군 $i$에 생애 주기 $C_i$를 준다. 여기에 개체군을 하나 더 추가하되, 모든 개체군의 생애 주기가 다시 맞아떨어질 때까지 걸리는 반복 횟수가 최대가 되도록 그 주기를 고른다. 모든 생애 주기가 맞아떨어질 때까지 개체군을 평가한 다음, 그 시점의 가장 좋은 해를 고른다. 답을 너무 오래 기다리는 것은 쓸모가 없으므로 반복 횟수에는 상한 $L$도 있다.

개체군들의 생애 주기와 반복 횟수 상한 $L$이 주어진다. 추가할 개체군의 최적 주기를 구한다.

첫째 줄에 정수 $N$과 $L$이 주어진다. $N$은 앞 단계에서 만들어진 개체군의 수, $L$은 반복 횟수의 상한이다 ($2 \le N \le 10^4$, $1 \le L \le 10^6$).

둘째 줄에 각 개체군의 생애 주기 길이 $C_i$가 $N$개 주어진다 ($1 \le C_i$). 지금 있는 개체군들의 생애 주기는 $L$번 이내의 반복에서 맞아떨어진다.

모든 개체군의 생애 주기가 맞아떨어질 때까지 걸리는 반복 횟수 $T$를 $T \le L$ 조건 아래에서 최대로 만드는 추가 개체군의 주기를 한 줄에 출력한다. 그런 주기가 여럿이면 가장 작은 값을 출력한다.