서브트랜스뮤테이션 timer 30s memory 1024MB

과학을 넘어선 힘이 필요한 상황이 또다시 찾아왔다. 당신은 나라에서 가장 뛰어난 연금술사로서, 희귀 금속에 대한 지도자의 끝없는 탐욕을 충족시키기 위해 소환되었다.

각 금속은 양의 정수 하나로 표현된다. 당신은 금속 1을 \mathbf{U_1}단위, 금속 2를 \mathbf{U_2}단위, ..., 금속 \mathbf{N}을 \mathbf{U_N}단위 만들어야 한다. 금속 \mathbf{N}+1, \mathbf{N}+2, \ldots도 존재하지만, 그 금속들을 특정 수량만큼 만들 필요는 없다. 또한 어떤 금속이든 필요한 양보다 더 많이 만들어도 되며, 초과분은 버리면 된다.

불행히도 예산 삭감으로 인해 당신은 단순한 연금술 주문 하나에 필요한 재료만 남게 되었다. 고정된 두 수 \mathbf{A}, \mathbf{B}(\mathbf{A} \lt \mathbf{B})에 대해, 당신은 금속 i 1단위를 파괴하여 금속 (i-\mathbf{A}) 1단위와 금속 (i-\mathbf{B}) 1단위를 만들 수 있다. 만약 결과 중 하나가 양수가 아니라면, 해당 단위는 생성되지 않는다. 특히 i \le \mathbf{A}이면 주문은 그 단위를 파괴하기만 하고 아무것도 만들지 않는다. 또한 \mathbf{A} \lt i \le \mathbf{B}이면 주문은 그 단위를 파괴하고 금속 (i-\mathbf{A}) 1단위만 생성한다.

당신에게는 숙련된 광부 한 명이 배정되었다. 이 광부는 당신이 원하는 어떤 금속이든 1단위만 가져올 수 있다. 그 1단위로부터 주문을 사용해 다른 금속을 만들고, 그렇게 만들어진 금속들에 다시 주문을 적용해 더 많은 단위를 만들어낼 수 있다. 아래 그림은 \mathbf{A}=1, \mathbf{B}=2인 주문을 두 번 사용하여 금속 4 1단위를 금속 1 1단위와 금속 2 2단위로 바꾸는 과정을 보여준다.

큰 정수로 표현되는 금속일수록 더 무겁고 다루기 어렵다. 따라서 당신은 광부에게, 당신의 임무를 완수하기에 충분한 금속 중 가장 작은 정수로 표현되는 금속 1단위를 가져오라고 요청하고 싶다. 그런 금속이 없다면 없다고 출력하라.