Problema número 491

Planificando las uvas

Tiempo máximo: 1,000 sMemoria máxima: 4096 KiB
Báscula antigua

Hoy es el último día del año y tú no faltarás a la cita con la tradición e intentarás comerte las doce uvas, una por cada una de las doce campanadas del reloj que marcarán el comienzo del nuevo año.

Llevas todo el año comiendo uvas cronómetro en mano. Tras muchas pruebas eres perfectamente consciente de tus limitaciones. Sólo llegas a tiempo a comerte la última uva con la última campanada si el peso total de las doce no excede un cierto umbral.

Ahora que ya está en casa el cesto con las uvas que se utilizarán te preguntas cuántas agrupaciones de uvas que cumplan tu restricción son posibles.

Entrada

La entrada estará compuesta por distintos casos de prueba, cada uno ocupando dos líneas.

En la primera línea del caso de prueba aparecen dos números con el peso máximo que has estimado que puedes comerte durante las campanadas y el número total de uvas que hay en casa (entre 12 y 24). La segunda línea contiene el peso de cada una de las uvas. Todos los pesos se miden con alta precisión, por lo que toman valores entre 1 y 109.

La entrada termina con una línea con dos ceros que no debe procesarse.

Salida

Por cada caso de prueba se escribirá de cuántas formas distintas puedes seleccionar las uvas sin superar el umbral marcado (y sin importar el orden).

Ten en cuenta que las uvas tienen pequeñas marcas que las hacen distinguibles unas de otras aunque pesen lo mismo.

Entrada de ejemplo

12 12
1 1 1 1 1 1 1 1 1 1 1 1 
12 24
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 
45 13
30 1 1 1 1 1 1 1 1 1 1 1 30
0 0

Salida de ejemplo

1
1
2