다트 챌린지

클라크와 해리는 형제입니다. 어릴 적부터 라이벌이었던 탓에, 두 사람의 아버지는 두 사람이 열세 살이 되던 해에 서로 다른 종목에 전념하도록 정했습니다. 성공을 두고 경쟁하지 않도록 하기 위해서였죠. 이제 스무 살이 된 두 사람은 각자 다른 분야에서 뛰어납니다. 클라크는 체스를 두고, 해리는 다트 대회에 나갑니다.

세 대회를 내리 우승한 해리는 자신만큼 성공하지 못한 클라크를 놀리기 시작했습니다. 클라크는 체스가 운의 요소가 적어 더 어렵다고 받아쳤습니다. 발끈한 해리는 다트를 최적으로 던지려면 상당한 조합론이 필요하다고 응수했고, 클라크는 싸늘하게 웃으며 온갖 마무리 수를 외우는 것을 조합론이라 부르긴 어렵다고 말했습니다.

그렇게 내기가 성사되었습니다. 해리는 외운 마무리 수가 통하지 않는 일반화된 다트판에서도 가능한 모든 마무리 점수를 찾아낼 수 있다고 장담했습니다. 하지만 클라크가 여러 다트판 목록을 보여주자, 해리는 자신이 감당하기 벅찬 일을 벌였음을 인정할 수밖에 없었습니다. 그의 친구인 당신이 도와주어야 합니다!

다트판은 여러 개의 영역(area)으로 이루어집니다. 각 영역에는 그 영역을 맞혔을 때 얻는 점수가 정해져 있습니다. 또한 각 영역에는 해당 점수의 2배, 3배에 해당하는 더블(double) 필드와 트리플(triple) 필드가 있습니다. 단 하나의 예외로, 가장 높은 점수를 가진 영역에는 더블 필드만 있고 트리플 필드는 없습니다. 각 영역의 점수가 주어질 때, 주어진 개수의 다트로 얻을 수 있는 서로 다른 총점의 개수를 구하세요.

다트를 한 번 던지면 다음 중 하나의 점수를 얻습니다.

• 판을 맞히지 못하면 $0$점
• 어떤 영역 $i$의 싱글을 맞히면 $s_i$점
• 어떤 영역 $i$의 더블을 맞히면 $2 \cdot s_i$점
• 가장 높은 점수의 영역을 제외한 어떤 영역 $i$의 트리플을 맞히면 $3 \cdot s_i$점

다트를 $k$개 던지면 총점은 각 다트가 얻은 점수의 합입니다(빗맞은 다트는 $0$점을 더합니다). 이렇게 만들 수 있는 서로 다른 총점이 몇 가지인지 세면 됩니다.

첫 번째 줄에 정수 $n$이 주어집니다. 이어지는 $n$개의 줄에는 각각 하나의 테스트 케이스가 주어집니다.

각 테스트 케이스는 두 정수 $a$와 $k$로 시작합니다($1 \le a \le 100$, $1 \le k \le 50$). $a$는 다트판의 영역 수, $k$는 던지는 다트의 개수입니다. 이어서 $a$개의 정수 $s_i$가 주어지며($1 \le s_i \le 100$), $s_i$는 영역 $i$를 맞혔을 때의 점수입니다. 모든 점수는 서로 다릅니다.

각 영역에는 더블 필드가 있고, 가장 높은 점수를 가진 영역을 제외한 모든 영역에는 트리플 필드도 있음을 기억하세요. 판을 맞히지 못하면 어떤 다트로든 항상 $0$점을 얻을 수 있습니다.

각 테스트 케이스에 대해 먼저 Scenario #i: 형식의 줄을 출력합니다. 여기서 $i$는 $1$부터 세는 시나리오 번호입니다. 그다음 줄에는 주어진 다트판에서 $k$개의 다트로 얻을 수 있는 서로 다른 총점의 개수를 출력합니다. 서로 다른 테스트 케이스의 출력 사이에는 빈 줄을 하나 넣어 구분합니다.