버스 노선
면접 대비시간 제한10초메모리 제한1024 MB
각 버스가 정해진 주기로만 운행하고 마감일 D가 주어질 때, 순서대로 모든 버스를 타고 D까지 도착할 수 있는 가장 늦은 출발일을 구한다. D에서 거꾸로 내려가며 각 주기의 최대 배수로 맞춘다.
문제
Bucket은 버스를 타고 시골을 가로지르는 아주 긴 여행을 계획하고 있다. 여행은 N개의 버스 노선으로 이루어지며, 타야 하는 순서대로 1번부터 N번까지 번호가 붙어 있다. 버스 자체는 매우 빠르지만 자주 다니지 않는다. i번째 버스 노선은 Xi일마다 한 번씩만 운행한다.
더 구체적으로, i번째 버스는 Xi일, 2Xi일, 3Xi일 등에만 탈 수 있다. 버스가 매우 빠르므로 같은 날에 여러 버스를 탈 수 있다.
Bucket은 D일까지 여행을 마쳐야 하지만, 가능한 한 늦게 출발하고 싶어 한다. D일까지 여행을 마치면서 첫 버스를 탈 수 있는 가장 늦은 날은 며칠인가?
Bucket이 D일까지 여행을 마칠 수 있는 경우만 입력으로 주어진다.
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 두 정수 N과 D가 주어진다. 그다음 줄에는 N개의 정수가 주어지며, i번째 정수는 Xi이다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 D일까지 여행을 마치면서 첫 버스를 탈 수 있는 가장 늦은 날이다.
제한
- 1 ≤ T ≤ 100.
- 1 ≤ Xi ≤ D.
- 1 ≤ N ≤ 1000.
- Bucket이 D일까지 여행을 마칠 수 있는 경우만 입력으로 주어진다.
힌트
예제 1에는 N = 3개의 버스 노선이 있고 Bucket은 D = 10일까지 도착해야 한다. 다음과 같이 탈 수 있다.
- 1번 버스를 6일에 탄다(X1 = 3),
- 2번 버스를 7일에 탄다(X2 = 7),
- 3번 버스를 8일에 탄다(X3 = 2).
예제 2에는 N = 4개의 버스 노선이 있고 Bucket은 D = 100일까지 도착해야 한다. 다음과 같이 탈 수 있다.
- 1번 버스를 99일에 탄다(X1 = 11),
- 2번 버스를 100일에 탄다(X2 = 10),
- 3번 버스를 100일에 탄다(X3 = 5),
- 4번 버스를 100일에 탄다(X4 = 50).
예제 3에는 N = 1개의 버스 노선이 있고 Bucket은 D = 1일까지 도착해야 한다. 다음과 같이 탈 수 있다.
- 1번 버스를 1일에 탄다(X1 = 1).