시장 투자 (라지)

면접 대비

시간 제한5초메모리 제한512 MB

요약

주어진 자금으로 살 수 있는 정수 수량을 기준으로 12개월 가격에서 이익이 최대인 매수 월과 이후 매도 월을 고합니다.

문제

투자할 수 있는 돈 $M$ 과 앞으로 1년 동안 매달 초 상품 가격을 예측한 값 $P_1, P_2, \dots, P_{12}$ 가 있다. 언제 사고 언제 팔아야 이익이 가장 커지는지 구하라.

거래 규칙은 다음과 같다.

매수는 딱 한 번만 한다. 달 $B$ 를 하나 고르고 ( $1 \le B \le 11$ ), 그 달의 가격 $P_B$ 로 상품을 산 뒤, 뒤의 달 $S$ 에 ( $B + 1 \le S \le 12$ ) 산 물량을 전부 판다.
상품은 개수 단위로만 살 수 있고 쪼개서 살 수 없다. 가진 돈으로 살 수 있는 최대 개수인 $\lfloor M / P_B \rfloor$ 개를 사고, 남은 돈은 그대로 둔다.
이 계획의 이익은 $\lfloor M / P_B \rfloor \times (P_S - P_B)$ 이다.

이익이 가장 큰 계획을 고른다. 이익이 같은 계획이 여러 개면 매수 단가 $P_B$ 가 더 낮은 쪽을 고르고, 그래도 같으면 $B$ 가 더 작은 쪽, 그다음으로 $S$ 가 더 작은 쪽을 고른다. 이익이 $0$ 보다 큰 계획이 하나도 없으면 이익을 낼 수 없다.

첫 줄에 테스트 케이스의 수 $N$ 이 주어진다.

각 테스트 케이스는 두 줄이다. 첫 줄에는 투자할 돈 $M$ 이 주어진다. 둘째 줄에는 각 달 초의 가격 $P_1, P_2, \dots, P_{12}$ 가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 한 줄에 Case #x: 를 먼저 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호다.

이어서 이익을 낼 수 없으면 IMPOSSIBLE 을 출력하고, 그렇지 않으면 다음 세 정수를 공백으로 구분해 출력한다.

예제 1

입력

3
100
1 2 3 4 5 6 7 8 9 10 11 12
100
52 50 25 100 61 63 70 51 71 55 10 5
100
200 150 250 132 125 110 210 220 180 176 108 113

예상 출력

Case #1: 1 12 1100
Case #2: 3 4 300
Case #3: IMPOSSIBLE

예제 2

입력

1
100
25 50 20 40 19 18 17 16 15 14 13 12

예상 출력

Case #1: 3 4 100

예제 3

입력

1
100
50 250 10 9 8 7 6 5 4 3 2 1

예상 출력

Case #1: 1 2 400