프로그래밍 대회 전략

프로그래밍 대회에 출전한 참가자로서, 정해진 대회 시간 안에 최대한 많은 문제를 풀되 총 시간은 가장 적게 만드는 것이 목표다.

각 문제를 푸는 데 걸리는 시간을 분 단위로 미리 정확히 예측했다고 하자. 푼 문제 수를 최대로 만들고, 그 조건에서 총 시간을 최소로 만드는 풀이 계획을 세우면 된다. 한 문제의 시간은 대회가 시작한 순간부터 그 문제를 제출한 순간까지 흐른 시간이고, 총 시간은 푼 모든 문제의 이 값을 더한 값이다. 계획을 세울 때는 모든 문제를 예측한 시간에 첫 제출로 맞힌다고 가정하므로 페널티 시간은 생각하지 않아도 된다. 한 번에 한 문제만 붙잡을 수 있고, 두 문제를 동시에 풀 수는 없다.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 20$)가 주어진다.

각 테스트 케이스는 두 줄이다. 첫째 줄에는 대회에 나온 문제 수 $N$ ($1 \le N \le 20$)과 대회 시간 $L$ ($1 \le L \le 1500$)이 공백을 사이에 두고 주어진다. 둘째 줄에는 각 문제의 예상 풀이 시간 $N$개가 공백을 사이에 두고 주어지며, 모두 $1$ 이상 $1500$ 이하의 정수다. 대회 시간과 예상 풀이 시간의 단위는 분이다.

각 테스트 케이스마다 Case x: a b c 형식으로 한 줄씩 출력한다. $x$는 $1$부터 시작하는 테스트 케이스 번호, $a$는 푼 문제 수, $b$는 마지막으로 푼 문제를 제출한 시각, $c$는 총 시간이다.

한 문제도 풀 수 없으면 $a$, $b$, $c$를 모두 $0$으로 출력한다.

첫 번째 예제의 첫 대회에는 문제가 6개(A부터 F까지) 나오고 대회 시간은 100분이다. 둘째 줄의 값이 각 문제의 예상 풀이 시간이므로 A는 15분, B는 23분, C는 41분이 걸린다.

이 대회에서 얻을 수 있는 가장 좋은 결과는 5문제다. 마지막 문제는 85분에 제출하고 총 시간은 228이 된다. C를 풀 시간은 남지 않는다.